[BOJ] 백준 3190 뱀 (JAVA)

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

3190번: 뱀

 

 

🔍 Solve

문제 그대로 따라 하는 시뮬레이션 문제입니다.

해당 문제는 방향을 전환하는 문제이므로, 방향 배열을 순서를 지켜서 만들어야 합니다.

저는 동->남->서->북 순서로 시계방향으로 돌아가는 순서로 만들었습니다.

방향을 전환할 때 L(왼쪽으로 90도)라면 방향 배열의 인덱스를 -1해주고, D(오른쪽으로 90도)라면 방향배열의 인덱스를 +1 해주었습니다. (0~4의 범위를 벗어날 때 예외처리 주의)

 

queue를 사용하여 뱀의 머리와 몸통, 꼬리를 관리해주었고, map배열에 뱀이 있는 위치는 1, 사과가 있는 위치는 2로 설정하여 관리했습니다.

queue를 사용하여 뱀의 머리가 갈 위치가 

1. 벽 ( !isIn(r, c) )

2. 뱀 자신의 몸통 ( map[r][c]==1 )

3. 사과 ( map[r][c]==2 )

4. 빈 곳

으로 나누어 해당 함수를 탈출하거나, queue, map을 처리해주었습니다.

 

해당 문제를 다 풀고 다른 분들의 풀이와 비교해보니 move함수를 time으로 반환하신 분들이 많았는데, 저는 time변수를 전역 변수로 설정하여 어떤 방법을 사용하시더라도 상관없을 것 같습니다.

 

또한, 저는 방향 정보를 HashMap을 사용하여 방향을 전환해야 할 time이 되었을 때 HashMap의 contains 메소드를 사용하여 편리하게 방향 정보를 받아왔습니다.

 

❗ Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //구현

    static int N; //보드의 크기
    static int K; //사과의 개수
    static int[][] map;  //1 : 뱀 위치, 2 : 사과 위치
    static int L; //뱀의 방향 변환 횟수
    static int[] dr = {0, 1, 0, -1};  //동>남>서>북
    static int[] dc = {1, 0, -1, 0};
    static int time;
    static HashMap<Integer, String> directs = new HashMap<>();  //배열대신 hashmap

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

        N = Integer.parseInt(br.readLine()); //보드의 크기
        K = Integer.parseInt(br.readLine()); //사과의 개수

        map = new int[N+2][N+2];  //r,c==0이거나 r,c==N+1이면 벽에 도착
        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; //사과
        }

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

        for(int i=0;i<L;i++){
            st = new StringTokenizer(br.readLine());
            int turn = Integer.parseInt(st.nextToken());
            String d = st.nextToken();

            directs.put(turn, d);

        }
        move();
        System.out.println(time);
    }

    private static void move(){
        Queue<Pos> queue = new LinkedList<>();

        queue.add(new Pos(1, 1));
        int d = 0; //오른쪽먼저
        int cr = 1;
        int cc = 1;
        map[1][1] = 1;  //뱀

        while(!queue.isEmpty()){
            time++;

            int nr = cr+dr[d];
            int nc = cc+dc[d];

            if(!isIn(nr, nc)) return;  //범위 벗어나면(벽에 부딪힘) 탈출
            if(map[nr][nc]==1){ // 뱀이 자기 몸에 부딪히면 탈출
                return;
            }

            if(map[nr][nc]==2){  //다음 위치가 사과면 머리만 길어짐
                queue.add(new Pos(nr, nc));
                map[nr][nc] = 1;
            }else{  //사과가 아니면
                queue.add(new Pos(nr, nc));  //머리 이동하고
                Pos remove = queue.poll();  //꼬리 자름
                map[nr][nc] = 1;  //뱀 머리위치 1로
                map[remove.r][remove.c] = 0;  //자른위치는 다시 0으로
            }

            if(directs.containsKey(time)){ //해시맵에 현재 시간이 포함되어있다면 방향 전환
                String dir = directs.get(time);
                if(dir.equals("L")){
                    d -= 1;
                    if(d<0){
                        d = 4+d;
                    }
                }else{
                    d = (d+1)%4;
                }
            }
            cr = nr;
            cc = nc;
        }
    }

    private static boolean isIn(int r, int c){
        return r>0 && c>0 && r<=N && c<=N;
    }


    private static class Pos{
        int r;
        int c;

        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public String toString() {
            return "Pos{" +
                    "r=" + r +
                    ", c=" + c +
                    '}';
        }
    }
}