[백준] 3190번 뱀

1:16

3190번: 뱀

• 사과를 먹으면, 뱀 길이가 늘어난다.
• 뱀이 기어다니다가 [ 벽 ] or [ 자기자신의 몸 ] 과 부딛히면 → 게임 END
• NxN 보드 위에서 진행되는 게임이 있다.
  • 몇 몇 칸 → 사과
  • 보드의 상하좌우 끝 : 벽
  • 맨 위 , 맨 좌측에서 시작 - 뱀의 길이 : 1
  • 맨 처음 : 오른쪽을 향한다
• 이동 규칙
  • 몸길이를 늘려, 머리를 다음 칸에 위치시킨다.
  • if 사과 O → 사과 없어지고, 꼬리는 움직이지 X : 몸 길이가 1 증가하는 것
  • else → 몸 길이를 줄인다 : 꼬리가 위치해있던 칸을 비워준다 : 몸 길이가 변하지 않는다.

문제를 이해하자

• 문제에는 [ 뱀의 방향 변환 횟수 ] 또한 주어진다.
  • X C : X초 후에, C로 회전시키는 것을 의미한다.
  • C는 'L' 또는 'D' 이다.
  • 'L' 은 왼쪽으로 90도 회전
  • 'D'는 오른쪽으로 90도 회전이다.
• 이 정보를 Queue에 넣어두고, 현재 시간을 Queue의 first와 비교한다. → 같은 경우, 방향을 전환시킨다.
• 따라서 현재 방향정보 또한 저장해 두어야 한다.

문제 풀이

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

public class Main{
    // ➡⬇⬆⬅ : 0,1,2,3
    public static int[][] moves = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
    // moves[0][0]는 현재 ➡방향일 때, C가 'D'인 경우, y는 curmoves[moves[0][0]][0]만큼 이동, x는 curmoves[moves[0][0]][1]만큼 이동
    public static int[][] dirs = new int[][]{ {1,2},{3,0},{0,3},{2,1} };
    // 현재 방향
    public static int curDir=0; // 시작 : ➡방향
    // board의 상태 : 2 -> 사과, 1 -> 뱀이 걸쳐져있는 칸임을 나타냄
    public static int[][] board;
    // 방향 전환정보 : FIFO  : 몇초후, 무슨방향(0:D, 1: L )
    public static Queue<int[]> q = new LinkedList<>();
    // 뱀의 정보
    public static Queue<int[]> snake = new LinkedList<>();
    // 보드의 크기 n , 사과의 개수 k
    public static int N;
    public static int k;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException {
        N = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        // ================ board init ==============
        board = new int[N][N];
        // 가장 좌측 , 맨 위 -> 뱀의 시작점
        board[0][0]=1;
        // 사과 정보 받기
        int r=0,c=0;
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken())-1;
            c = Integer.parseInt(st.nextToken())-1;
            board[r][c]=2;
        }
        // 방향 정보 받기
        int l=0,s=0,dir=0;
        String temp;
        l = Integer.parseInt(br.readLine());
        for(int i=0;i<l;i++){
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            temp = st.nextToken();
            if(temp.equals("D"))dir =0;
            else dir =1;
            q.add(new int[]{s,dir});
        }
        snake.add(new int[]{0,0});
    }
    public static int solve(){
        int r=0,c=0;
        int s=0;
        int[] del =null,temp = null;
        // curDir을 이용하여 이동한다 : 매 번 q의 가장 앞에 있는 원소의 시간과 비교한다.
        while(true){
            s++;
            // curDir
            r+=moves[curDir][0];
            c+=moves[curDir][1];
            // 벽이거나 뱀의 몸과 같은 곳 -> end
            if(r<0 ||c<0||r>=N||c>=N||board[r][c]==1) break;

            // 뱀의 위치 정보를 put
            snake.add(new int[]{r,c});

            // 사과가 있다면 몸을 늘린다
            // 사과가 없다면 수축
            if(board[r][c]!=2){
                del = snake.poll(); // 뱀의 정보에서 delete
                board[del[0]][del[1]]=0; // board에서 빈 칸으로 update
            }
            board[r][c]=1;
            // s초가 끝난 뒤 , q의 값과 비교한다.
            if(q.isEmpty()==false&&q.peek()[0]==s){
                // q의 값과 같은 경우 -> 방향을 전환한다
                temp = q.poll();
                // temp[1]
                // dirs[curDir][temp[1]]
                curDir = dirs[curDir][temp[1]];
            }
        }
        return s;
    }
    public static void main(String[] args)throws IOException {
        setting();
        int sec = solve();
        System.out.println(sec);

    }
}