백준 3190번 : 뱀 java

이 문제는 사과가 있는 곳을 입력받아서 뱀이 사과가 있는 곳을 지나치면 뱀의 길이를 늘이고 아니면 유지하게 합니다.

그리고 시간이 경과함에 따라서 방향을 회전시키게 해서 뱀이 벽이나 자신의 몸에 머리를 박으면 게임이 끝나게 합니다.

이 문제를 예제 1번을 이용하여 설명드리겠습니다.

예제 1번의 초기 상태는 다음과 같습니다.

위에 spin 큐에 들어가 있는 것들은 X초 후에 어떤 방향으로 회전하는가를 나타냅니다.

L이면 보고 있는 방향의 왼쪽으로 회전, D면 오른쪽으로 회전합니다.

사과를 먹으면 길이가 늘어나고 먹지 않으면 길이를 유지합니다.

이제 뱀을 이동시켜보겠습니다.

우선 문제의 조건에 맞게 뱀을 한 칸 앞으로 보냈습니다.

그러나 사과를 먹지 않았으므로 길이가 늘지 않아  빨간 화살표를 지워줍니다.

다시 한번 이동시켜 주겠습니다.

이번에도 사과를 먹지 못해서 길이가 늘지 않았습니다.

이번에도 사과를 먹지 않아서 길이가 그대로 입니다.

그런데 이 뱀이 이동한 지 이제 3초가 지났습니다.

spin 큐에 들어가 있는 첫 번째 노드가 3초 후에 보는 방향의 오른쪽으로 뱀을 회전시키라고 합니다.

따라서 저는 이에 따라서 뱀을 회전시키겠습니다.

spin 큐의 첫 번째 노드를 사용하였기 때문에 poll해줍니다.

이제 다시 뱀을 이동시키겠습니다.

다음 이동할 때는 뱀이  사과를 먹게 됩니다.

따라서 뱀의 길이가 길어지므로 이전에 있던 자리에도 뱀을 남겨줍니다.

이제 뱀을 계속 이동시켜주도록 하겠습니다.

이제 다음으로 이동하면 뱀이 벽에 머리를 박아 게임이 끝나게 됩니다.

따라서 걸리는 시간은 9입니다.

이제 이 알고리즘을 코드로 구현해보도록 하겠습니다.

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        int[][] map = new int[N+1][N+1];

        //사과가 있는 위치는 1로 초기화
        for(int i = 0; i<K; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());

            map[row][col] = 1;
        }

        int L = Integer.parseInt(br.readLine());

        //시간에 따라서 회전시킬 방향 queue 생성
        Queue<spin> spin = new LinkedList<>();
        for(int i = 0; i<L; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int time = Integer.parseInt(st.nextToken());
            String dir = st.nextToken();

            spin.offer(new spin(time, dir));
        }

        //0은 북, 1은 동, 2는 남, 3은 서 의미
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};

        //초기 (1, 1)에서 시작하고 동쪽을 보고 시작
        int row = 1;
        int col = 1;
        int time = 0;
        int dir = 1;
        Queue<Node> q  = new LinkedList<>();
        q.offer(new Node(row, col));
        map[row][col] = 2;

        while(true){
            int dR = row + dr[dir];
            int dC = col + dc[dir];

            time++;

            if(dR<1||dC<1||dR>N||dC>N)
                break;
            if(map[dR][dC] == 2)
                break;

            if(map[dR][dC] == 0){
                Node node = q.poll();
                map[node.row][node.col] = 0;
            }
            if(!spin.isEmpty()) {
                if (time == spin.peek().time) {
                    spin s = spin.poll();

                    if (s.dir.equals("L"))
                        dir = dir-1 < 0 ? 3 : dir-1;
                    if (s.dir.equals("D"))
                        dir = dir+1 > 3 ? 0 : dir+1;
                }
            }

            map[dR][dC] = 2;
            q.offer(new Node(dR, dC));
            row = dR;
            col = dC;
        }

        System.out.println(time);
    }
}
class spin{
    int time;
    String dir;

    spin(int time, String dir){
        this.time = time;
        this.dir = dir;
    }
}

class Node{
    int row, col;

    Node(int row, int col){
        this.row = row;
        this.col = col;
    }
}

저는 뱀이 있는 자리를 2로 사과가 있는 공간을 1로 초기화시키며 뱀이 있는 공간을 큐에 담았습니다.

그리고 사과를 먹지 않았을 때는 큐를 poll해주어 뱀의 꼬리 부분을 다시 비어 있는 공간으로 만들었습니다.