3190 - 뱀 [성공(반례힌트)|02:14:43]

문제🦖 핵심 키워드

 

1. N*N 크기의 보드가 주어짐 (2 <= N <= 100)
2. 뱀은 매 초마다 다음 규칙으로 이동
3. 이동 경로가 주어질 때 몇 초에 끝나는가?
4. 사과의 개수 K (0 <= K <= 100)
5. 방향 변환 정보 L (1 <= L <= 100)

 

 

💡아이디어

 

이 문제를 풀기 전에 다른 문제의 큰돌님 강의 해설에서 보드를 돌리는 방법으로 문제를 푸는 해설을 보았다. 그 영향으로 처음에 이 문제도 오른쪽으로 회전이면 보드를 오른쪽으로 90도 돌리고 왼쪽으로 회전이면 보드를 왼쪽으로 90도 돌리는 로직을 생각했다. 그래서 이 로직에 대한 시간복잡도를 계산해보았다.

1. 최대 100번의 방향 변환 횟수
2. 보드를 돌리기 위한 로직 100*100
3. 시간의 최댓값은 적어도 10000

그럼 총 10000 * 100 * 10000 = 10000000000으로 약 100억이다. 이 방법은 안될 것 같다.

 

그래서 두 번째로 생각해낸게 그냥 dx, dy 배열을 이용해서 index 값을 두고 좌로 전환 시 -1, 우로 이동 시 +1을 하도록 구성하는 것이다. 그럼 보드를 돌리는 로직 자체가 없어지므로 위의 시간 복잡도에서 100 * 10000 = 1000000으로 상당히 줄어드는 것을 알 수 있다.

 

어떻게 움직일지는 대충 정했으니 문제의 규칙에서 움직였는데 사과를 먹지 못했을 때 꼬리를 어떻게 지워줄지 생각했다. 이건 비교적 간단하게 떠올릴 수 있었는데 ArrayDeque를 활용해 지나가는 좌표값을 담아가면서 0을 만나는 순간 처음 담은 좌표의 값부터 이동마다 하나씩 0으로 만들어주면 되는 것이었다.

 

이 핵심 두 가지만 잘 파악하면 쉽게 풀 수 있는 문제였는데 처음 생각해낸 방법을 시간 복잡도 고려하지 않고 구현해보려다 2시간을 훌쩍 넘겨버렸다.

 

 

코드

public class N_BOJ_3190 {
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};

    static int[][] map;
    static char[] time;
    static int N, K, L;

    static ArrayDeque<Integer> q = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            map[y-1][x-1] = 1;
        }

        L = Integer.parseInt(br.readLine());
        time = new char[10001];
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());

            int t = Integer.parseInt(st.nextToken());
            char c = st.nextToken().charAt(0);
            time[t] = c;
        }

        int d = 0;
        int y = 0, x = 0;
        map[0][0] = 2;
        q.add(0);
        q.add(0);

        for (int t = 0; t < 10001; t++) {

            if (time[t] == 'D')
                d = (d + 1) % 4;
            else if (time[t] == 'L')
                d = (d - 1) < 0 ? 3 : d-1;

            int ny = y + dy[d];
            int nx = x + dx[d];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N ||
                map[ny][nx] == 2) {
                System.out.println(t + 1);
                return;
            }

            if (map[ny][nx] == 0) {
                int yy = q.poll();
                int xx = q.poll();
                map[yy][xx] = 0;
            }

            map[ny][nx] = 2;
            q.add(ny);
            q.add(nx);

            y = ny;
            x = nx;
        }
    }
}

 

이렇게 풀고나서 큰돌님 강의 해설을 봤는데 시간 기준에 따라 방향 전환을 코드에 먼저 둘 수도 있고 나중에 둘 수도 있었다. 사실 이게 이해가 안가서 좀 힘들었다. 예를 들어 8초에 왼쪽으로 방향 전환하는 조건이 있다면, 큰돌님 코드는 8초에 7초의 정보를 가지고 8초의 위치로 이동하기 때문에 이동 이후에 방향 전환을 해주는 것이고 반면에 내가 작성한 코드는 8초에서 9초의 이동 좌표를 계산하기 때문에 미리 방향전환을 먼저 해줬어야 하는 것이다!!