[백준 3190번] 뱀

https://www.acmicpc.net/problem/3190

 

package datastructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class DataStructure3190 {
    static int N;

    static int[][] map;
    static Queue<Object[]> state;


    // 북 동 남 서
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        StringTokenizer st;

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 사과 배정
            map[x - 1][y - 1] = 2;
        }

        int L = Integer.parseInt(br.readLine());
        state = new LinkedList<>();
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            String alarm = st.nextToken();
            state.add(new Object[]{cnt, alarm});
        }

        System.out.println(bfs());
    }

    public static int bfs() {
        Deque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[]{0, 0});
        int time = 0;
        int dir = 1;

        while (!deque.isEmpty()) {
            int[] poll = deque.peekLast();
            int x = poll[0];
            int y = poll[1];

            // 방향 전환
            if (!state.isEmpty()) {
                Object[] peek = state.peek();
                if (time == (int) peek[0]) {

                    if (peek[1].equals("D")) {
                        dir = dir + 1 > 3 ? 0 : dir + 1;
                        //System.out.println(x + " " + y);
                    } else if (peek[1].equals("L")) {
                        //System.out.println(x + " " + y);
                        dir = dir - 1 < 0 ? 3 : dir - 1;
                    }
                    state.poll();
                }
            }



            //이동
            int nX = x + dx[dir];
            int nY = y + dy[dir];

            // 벽
            if (nX >= N || nY >= N || nX < 0 || nY < 0) {
                break;
            }
            // 내 자신
            if (map[nX][nY] == 1) {
                break;
            }
            // 사과
            if (map[nX][nY] == 2) {
                map[nX][nY] = 1;
                deque.add(new int[]{nX, nY});
            } else {

                int[] first = deque.poll();
                map[first[0]][first[1]] = 0;
                map[nX][nY] = 1;
                deque.add(new int[]{nX, nY});
            }


            time++;
        }

        return time + 1;
    }


}

 

 

 

방향 때문에 헷갈렸던 문제이다. 남쪽으로 가다가 L을 만나면 동쪽으로 돌아서야 하는데, 이 과정을 어떻게 구현할지 고민이 많았다. 그래서 삼항 연산자를 사용하여 D일 때는 dist + 1 > 3, L일 때는 dist - 1 < 0을 이용해 방향을 구했다. Deque를 사용하는 이유는 요소들이 이동할 때마다 위치를 저장하고, 마지막 위치를 이용해 방향을 계산해야 하기 때문이다. 또한, 이동 후에는 맨 앞 요소를 삭제해야 하기 때문에 Deque가 적합했다.

 

 

근데 솔직히 다 쉬었고 사실상 이 문제의 핵심은 방향 전환이다.