[백준 3190번] 뱀 :: 늦깎이 IT

[백준 3190번] 뱀

1. 뱀의 몸통 좌표를 Deque 자료구조를 활용해서 저장한다. 머리를 움직일 때에는 Deque의 first에 추가하고 뱀의 꼬리를 자를 때는 Deque의 last에서 삭제한다.

2. 뱀의 전체 몸통이 차지하는 부분을 체크하기 위해 visited 배열을 선언하고, 뱀의 몸통이 위치한 자리마다

true로 체크한다.

3. 현재 이동방향에 따라 머리를 한칸 전진시킨다.

1) 머리를 전진시켰을 때, 이미 visited[row][col] = true이면, 뱀의 머리가 뱀의 몸통 중 일부를 만났다는 것이므로 종료한다.

2) 머리를 전진시켰을 때, 사과가 있다면 뱀의 꼬리를 자르지 않는다.

3) 머리를 전진시켰을 때, 빈칸이라면 꼬리를 자른다.

4) 머리를 전진시켰을 때, 벽이라면 종료한다.

4. 현재 이동시간이 입력에서 주어지는 방향을 바꿔야하는 시간과 같다면, 입력에 따라 이동방향을 바꿔준다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, K, L;
    public static int[][] map;
    public static boolean[][] visited;
    public static Move[] move;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동 서 남 북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visited = new boolean[N][N];
 
        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            map[row - 1][col - 1] = 1;
        }
 
        L = Integer.parseInt(br.readLine());
        move = new Move[L];
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
            move[i] = new Move(time, dir);
        }
        System.out.println(solve());
    }
 
    public static int solve() {
 
        int curDir = 0;
        int curTime = 1;
        int idx = 0;
 
        Deque<Node> q = new ArrayDeque<>();
        q.offerFirst(new Node(0, 0));
        visited[0][0] = true;
 
        while (true) {
 
            Node head = q.peekFirst();
            int nr = head.row + dirX[curDir];
            int nc = head.col + dirY[curDir];
 
            // 벽을 만났을 경우
            if (!isBoundary(nr, nc))
                return curTime;
 
            // 뱀의 몸통을 만났을 경우
            if (visited[nr][nc])
                return curTime;
 
            // 사과를 만났을 경우
            if (map[nr][nc] == 1) {
 
                // 꼬리를 자르지 않고, 머리에 추가한다.
                map[nr][nc] = 0;
                q.offerFirst(new Node(nr, nc));
                visited[nr][nc] = true;
 
            } else { // 빈칸일 경우
 
                // 머리를 한칸 전진시키고, 꼬리를 자른다.
                Node tail = q.pollLast();
                visited[tail.row][tail.col] = false;
 
                q.offerFirst(new Node(nr, nc));
                visited[nr][nc] = true;
            }
 
            // 입력으로 주어진, 방향을 바꿔야할 시간이 되면 방향을 바꿔준다.
            if (idx < L && curTime == move[idx].time) {
                curDir = getNextDirection(curDir, move[idx].dir);
                idx += 1;
            }
 
            curTime += 1;
        }
 
    }
 
    public static int getNextDirection(int curDir, char dir) {
 
        // 오른쪽으로 회전
        if (dir == 'D') {
            if (curDir == 0)
                return 2;
            else if (curDir == 1)
                return 3;
            else if (curDir == 2)
                return 1;
            else
                return 0;
        } else {
            if (curDir == 0)
                return 3;
            else if (curDir == 1)
                return 2;
            else if (curDir == 2)
                return 0;
            else
                return 1;
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
}
 
class Node {
 
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}
 
class Move {
 
    int time;
    char dir;
 
    public Move(int time, char dir) {
        this.time = time;
        this.dir = dir;
    }
 
}