[BOJ 3190] 뱀

문제

• BOJ 3190
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

수업시간에 안풀고 오늘 처음 풀어봤는데 정답률에 비해 큰 함정은 없던 문제이다.
1초동안 해야할 일은 크게 두가지이다.

1. 뱀을 이동시키고 사과가 있으면 길이 증가, 사과가 없으면 길이 고정
   • 다음 좌표가 벽이 아니고 뱀 자신이 아니면 현재 좌표를 다음 좌표로 이동시킨 후,
     해당 좌표를 뱀이 차지하고 있는 좌표를 관리하는 queue에 넣어줌
   • 사과가 있으면(입력받을때 사과 좌표는 map[i][j]==-2로 표시해둠),
     length증가시키고 다음 머리 좌표에 뱀이 있음을 표시 map[i][j]=-1
   • 사과가 없으면,
     현재 꼬리좌표에 뱀 표시를 삭제해줘야하므로 queue에서 하나 꺼내서 해당 좌표값을 0으로 만듦
     이 경우도 머리 좌표는 이동하므로 뱀이 있으믈 표시 map[i][j]=-1
2. 현재 초에 바꿔야 할 방향 전환 정보가 Map에 있으면 rotate 변수를 바꾼다.
   • 처음엔 오른쪽을 바라보고 있으므로 dir이 1
   • rotate변수에 따라서 dir을 시계방향 or 시계 반대방향으로 바꿔준다.
   • dir은 di,dj배열의 인덱스에 해당

꼬리좌표는 뱀이 차지하고 있는 좌표 중 가장 오래된 좌표이기 때문에 큐를 사용해서 뱀 좌표들을 관리해주었다.

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

//뱀
public class Main {

    static int N; //보드크기
    static int K; //사과개수
    static int L; //방향 변환 횟수
    static int[][] map;
    static Map<Integer, Character> timeInfo; //특정시간이후 방향정보
    static int hx=1, hy=1; //머리 좌표
    static char rotate = 'D'; //회전 방향
    static int dir = 1; //현재 방향
    static int length = 1; //현재 뱀 길이
    static Queue<Point> queue; //꼬리 좌표 관리 큐
    static int time=1; //시간
    static int[] di = {-1, 0, 1, 0}; //북동남서
    static int[] dj = {0, 1, 0, -1};

    static class Point{
        int x;
        int y;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

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

        for(int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[r][c] = -2; //사과표시
        }//input 사과

        L = Integer.parseInt(br.readLine());
        timeInfo = new HashMap<>();

        for(int i=0; i<L; i++){
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            char direction = st.nextToken().charAt(0);
            timeInfo.put(time, direction);
        }//input 방향

        queue = new LinkedList<>();
        queue.add(new Point(1,1));
        map[1][1] = -1; //뱀 표시

        while(true){
            int nhx, nhy = 0; //다음 좌표

            nhx = hx + di[dir];
            nhy = hy + dj[dir];


            //벽 또는 자기자신과 안 부딪힌다면
            if(nhx>=1 && nhx<=N && nhy>=1 && nhy<=N && map[nhx][nhy]!=-1){
                hx = nhx;
                hy = nhy;
                queue.add(new Point(hx, hy));
                if(map[nhx][nhy] == -2){//사과가 있다면 길이 증가
                    map[hx][hy] = -1;
                    length++;
                }else{//꼬리 앞으로
                    //현재 꼬리 찾기
                    map[hx][hy] = -1;
                    Point p = queue.poll();
                    map[p.x][p.y] = 0;
                }
            }else{
                break;//게임 종료
            }
            //방향 전환해야 하는지 체크
            if(timeInfo.containsKey(time)){
                rotate = timeInfo.get(time);
                if(rotate=='D'){ //회전 시계방향
                    dir = (dir+1)%4;
                }else{//반시계 방향
                    dir = (dir+3)%4;
                }
            }
            time++;
        }

        System.out.println(time);


    }
}