백준, 뱀(3190, java)

문제 설명

사과를 먹으면 몸의 길이가 늘어나는 뱀이 있다. 뱀이 이리저리 돌아다니다가 자기 자신 혹은 벽과 부딪히면 게임이 끝이 난다. 이때 게임이 몇 초에 끝나는지 구하는 문제이다.

 

조건

1. 뱀은 머리를 늘려 다음 칸에 머리를 위치시킨다.

2. 만일 다음 칸이 벽이거나 칸에 자기 자신이 있을 경우 게임이 중료된다.

3. 만일 2번 조건이 아니고 다음 칸에 사과가 있을 경우 사과를 먹는다. 사과가 없다면 꼬리를 한 칸 줄이는데 이경우 몸 길이를 유지한다.

 

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

3190번: 뱀

주의 사항 입력을 받을 때 X초가 끝난 후 C로 방향을 움직이게 되어있다. 그러므로 직전 방향을 유지하며 X초 이동하고 C 방향으로 움직이면 된다.

 

또한 게임이 종료되는 경우는 다음 칸이 벽이거나 자기 자신일 때이다. 그러므로 해당 조건이 맞지 않다면 계속해서 변환 정보를 반복해줘야 한다.

 

아! 그리고 8, 10, 11, 13이렇게 차례대로 X가 나올 것이다. 이는 첫 번째 이동을 8초 하고 10초 하고... 이런 의미가 아니라 8초 이동 (10-8) = 2초 이동 (11-10) = 1초 이동. 이렇게 초가 누적이 되는 거다.

문제 풀이

설명하기 전에

처음 문제를 봤을 때는 간단한 너비우선탐색 문제인 줄 알았다. 그러나 예상보다 조건이 까다로워 시간이 꽤 걸렸다.

 

문제를 설명하기 전에 먼저 문제의 조건을 다시 생각하고 넘어가겠다.

 

일단 게임이 끝나는 경우는 다음 칸에 자기 자신이 존재하거나 벽이 있는 상황이다. 그러므로 방향 변환 횟수 L을 모두 탐색했더라도 게임이 끝나는 조건에 도달하지 못한다면 다시 변환 횟수를 돌려줘야 한다.

 

또한 X초 이동한 후 C 방향으로 90도 이동에서 X초는 누적이 된다. 문제의 예시처럼 '3 D', '15 L'이렇게 되어 있다면 3초 만큼 이동하고 'D' 방향으로 90도 이동 후 15초 이동하고 'L' 방향으로 90도 이동이 아니라, 3초 이동한 후 'D' 방향으로 90도 이동하고 12초 이동한 후 'L' 방향으로 90도 이동이다. 즉, 초가 누적이 된다고 생각하면 된다. 문제에서 방향 전환 정보는 X가 증가하는 순으로 주어진다는 게 그런 이유이다.

 

질문 1, 뱀의 몸통 위치를 어떻게 표시할 것인가?

이 문제의 핵심은 뱀의 몸통 위치라고 생각한다. 이유는 뱀의 몸통 위치를 어떻게 표시하냐에 따라서 답이 갈리기 때문이다.

 

나는 초반에는 직접 map에 뱀의 몸통 위치를 하나씩 넣어줬다. 하지만, 이렇게 하면 너무 많은 경우의 수를 따져줘야 해서 효율이 좋지 않다. 

 

그렇다면 어떻게하면 뱀의 몸통 위치를 효율적으로 표시할 수 있을까?

문제에서는 먼저 뱀이 새로운 칸으로 머리를 이동한 다음, 사과의 유무에 따라 유지하거나 꼬리를 줄인다고 했다. 즉, 새로운 칸이 들어오고 제일 마지막에 들어온 칸이 나가는 구조이다. 선입선출 영어로 하자면  first in first out. 어디서 많이 보지 않았는가? 바로 큐이다.

 

하지만, 나는 큐 대신  덱을 사용했다. 그 이유는 하나의 변환이 끝나면 다시 뱀의 머리를 찾아 시작해줘야 하기 때문에 양 옆에서 넣고 뺄 수 있는 자료구조를 선택했다.

질문 2, 90도 돌아가는 방향은 어떻게 계산할 것인가?

이 부분은 예상 외로 간단한데 mod를 써주면 된다. 'D'로 오른쪽 90도 회전을 할 때는 (현재 방향+1)%4이고 왼쪽 90도 회전은 (현재 방향+3)%4로 방향을 찾아주면 된다.

질문 3, 시간의 누적은 어떻게 계산할 것인가?

위에서 말했듯이 X는 누적이 되는 시간이다. 그러므로 n+1의 시간 빼기 n의 시간 이렇게 하면 필요한 시간을 구할 수 있다. 그러나 한 텀이 끝나고 다음 텀으로 넘어갈 때는 바로 직전의 시간이 현재 시간보다 크기 때문에 바로 직전의 시간을 0으로 표시해서 음수가 나오는 경우를 걸러준다.

코드

java

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

import java.util.*;

class pair{
    int row;
    int col;
    //int d;
    pair(int row, int col){
        this.row = row;
        this.col = col;
    }
}

class directionPair{
    int X;
    String C;
    directionPair(int X, String C){
        this.X = X;
        this.C = C;
    }
}

public class Main {

    //남동북서
    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};
    public static int[][] map;
    public static int N;

    public static Deque<pair> snake;
    public static Queue<directionPair> directionList;
    public static int startRow, startCol, tailRow, tailCol;
    public static int answer;

    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];
        answer = 0;
        snake = new LinkedList<>();
        directionList = new LinkedList<>();
        int startTime = 0;

        //1이 사과 2가 자기 자신
        for(int i=0; i<K; i++){
            String[] input1 = br.readLine().split(" ");
            int c = Integer.parseInt(input1[0])-1;
            int r = Integer.parseInt(input1[1])-1;

            map[c][r] = 1;
        }

        int L = Integer.parseInt(br.readLine());
        //방향은 처음에는 오른쪽 -> 동
        int lastD = 1;
        for(int i=0; i<L; i++){
            String[] input2 = br.readLine().split(" ");
            int x = Integer.parseInt(input2[0]);
            String c = input2[1];
            directionList.add(new directionPair(x, c));
            if(i == 0){
                startTime = x;
            }
        }


        int d = 1;
        int lastTime = 0;
        snake.add(new pair(0, 0));
        while(true){
            directionPair dP =  directionList.poll();
            int time = dP.X;
            if(time == startTime){
                lastTime = 0;
            }
            if(!bfs(time-lastTime, d)){
                break;
            }

            d = checkDirection(dP.C, d);
            lastTime = time;
            directionList.add(dP);
        }

        System.out.println(answer);

    }

    //
    public static int checkDirection(String c, int d){
        if(c.equals("D")){
            return (d+1)%4;
        }else{
            return (d+3)%4;
        }
    }

    public static boolean checkSnake(int targetRow, int targetCol){
        Queue<pair> tmp = new LinkedList<>();
        while(!snake.isEmpty()){
            pair tmpPair = snake.poll();
            //System.out.println(tmpPair.row + " " + tmpPair.col);
            if (tmpPair.row == targetRow && tmpPair.col == targetCol) {
                return false;
            }
            tmp.add(tmpPair);
        }

        while(!tmp.isEmpty()){
            snake.add(tmp.poll());
        }
        return true;
    }

    public static boolean bfs(int time, int d){
        Queue<pair> queue = new LinkedList<>();
        pair start = snake.removeLast();
        queue.add(new pair(start.row, start.col));
        snake.add(start);

        while(queue.size() != 0) {
            if (time == 0) {
                break;
            }
            answer += 1;
            //System.out.println();
            time -= 1;
            pair current = queue.poll();
            int nRow = current.row + dR[d];
            int nCol = current.col + dC[d];
            //System.out.println(time + " " + d);

            if (nRow >= 0 && nRow < N && nCol >= 0 && nCol < N) {
                if (checkSnake(nRow, nCol)) {
                    //System.out.println(nRow + " " + nCol);
                    //만일 새로 간 곳에 사과가 존재한다면
                    if (map[nRow][nCol] == 1) {
                        //몸을 표시하고 큐에 넣는다.
                        map[nRow][nCol] = 0;
                        queue.add(new pair(nRow, nCol));
                        snake.add(new pair(nRow, nCol));
                    }else{
                        //새로 간 곳에 사과가 없음
                        //map[nRow][nCol] = 2;
                        snake.add(new pair(nRow, nCol));
                        //System.out.println(snake.size());
                        snake.poll();
                        queue.add(new pair(nRow, nCol));
                    }
                } else {
                    //System.out.println("사과 혹은 자기 자신");
                    return false;
                }
            } else {
                //System.out.println("범위를 벗어남");
                return false;
            }


            //display();


        }
        return true;
    }



}