[백준 / Java] 3190: 뱀 (시뮬레이션, 자료구조)

난이도: Gold 4

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

 

 

머리를 늘리고 꼬리를 자르면 되는 문제이다.

일단 뱀과 사과 정보를 저장할 2차원 배열을 만들자.

 

 

2차원 배열을 만들고 뱀의 몸이 있는 칸을 1, 사과가 있는 칸을 2로 설정해놓았다.

뱀이 사과가 있는 칸에 도달하면 2가 있던 칸이 1로 바뀌고 점점 1의 개수가 늘어나게 된다.

그리고, 이 게임이 몇 초 경과하고 끝이 나는지 계산할 second 변수를 만들었다.

 

 

사과가 없으면 1은 계속 그냥 이동하고, 사과가 있으면 2가 있던 칸을 1로 만들고 이동하면 된다.

이렇게 하면 1이 점점 많아지게 된다.

이 경우에는 9번 움직인 뒤 벽에 부딫쳐서 게임이 끝나므로 9초 뒤에 끝이 나게된다.

 

 

이 문제는 맨 앞에 요소를 추가하고, 맨 뒤 요소를 제거해야 하므로 Deque를 사용해야 한다.

N * N의 2차원 배열을 만들고,

뱀의 방향 변환 정보를 저장할 HashMap<Integer, Charager>을 만들고,

뱀의 행, 열, 방향 정보를 가지고 있는 객체 타입의 Deque를 만들면 된다.

 

이렇게 설정을 해 놓고 문제에서 하라는 데로만 하면 풀린다.

static class Snack {
        int r;    // 뱀의 행 위치
        int c;    // 뱀의 열 위치
        int d;    // 뱀의 방향 (0: 북, 1: 동, 2: 남, 3: 서)
        
        Snack(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
}

 

뱀의 행, 열, 방향 정보를 가지고 있는 객체는 위와 같다.

(지금 봤는데 뱀의 영어 스펠링인 Snake가 아니라 Snack으로 잘못 적어놨네...)

 

 

주석에 설명을 한 줄 한 줄 자세하게 적어놓았다.

자, 그럼 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class P3190_뱀 {
    static int N;            // 보드의 크기
    static int[][] board;    // 2차원 N * N 크기의 보드
    
    static class Snack {
        int r;    // 뱀의 행 위치
        int c;    // 뱀의 열 위치
        int d;    // 뱀의 방향 (0: 북, 1: 동, 2: 남, 3: 서)
        
        Snack(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
    
    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());    // 사과의 개수
        board = new int[N + 1][N + 1];
        HashMap<Integer, Character> change = new HashMap<>();    // 뱀의 방향 변환 정보    
        int second = 0;        // 게임 경과 시간
        
        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());    // 사과의 행 위치
            int c = Integer.parseInt(st.nextToken());    // 사과의 열 위치
            board[r][c] = 2;
        }
        
        int L = Integer.parseInt(br.readLine());    // 뱀의 방향 변환 횟수
        
        for (int i = 0; i < L; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());    // X초가 끝난 뒤
            char C = st.nextToken().charAt(0);    // 왼쪽(L) 또는 오른쪽(D)으로 90도 방향 회전
            change.put(X, C);    // 뱀의 방향 변환 정보 삽입
        }
        
        Deque<Snack> deque = new ArrayDeque<>();
        deque.add(new Snack(1, 1, 1));    // 뱀의 맨 처음 위치(1행 1열), 뱀의 맨 처음 방향(1: 동쪽)
        board[1][1] = 1;    // 뱀의 처음 위치
        
        while (!deque.isEmpty()) {            
            Snack now = deque.peek();    // 현재 뱀의 머리
            second++;                    // 1초 경과
            
            // 앞으로 갈 수 있으면 뱀의 머리 객체 리턴
            Snack next = goStraight(now.r, now.c, now.d);    
            
            if (next == null) {    // 앞으로 이동한 곳이 벽이거나 자기자신의 몸이라면 이동 불가
                break;            // 게임 종료
            } else {    // 앞으로 이동한 곳이 벽이 아니고, 자기자신의 몸도 아니라면 이동 가능
                // 현재 경과 시간에 방향을 회전시켜야 하는지 확인하기
                if (change.containsKey(second)) {    
                    char C = change.get(second);    // 변환해야 할 방향 가져오기
                    if (C == 'L') {            // 왼쪽으로 회전해야 할 때
                        next.d = (next.d == 0) ? 3 : next.d - 1;
                    } else if (C == 'D') {    // 오른쪽으로 회전해야 할 때
                        next.d = (next.d == 3) ? 0 : next.d + 1;
                    }
                }
                
                deque.addFirst(next);    // 몸 길이를 늘려 머리를 다음 칸에 위치시키기
                
                if (board[next.r][next.c] == 2) {    // 이동한 칸에 사과가 있다면
                    // 그 칸에 있던 사과가 없어지고 해당 칸이 자기자신의 몸으로 바뀜
                    board[next.r][next.c] = 1;
                } else {    // 이동한 칸에 사과가 없다면
                    board[next.r][next.c] = 1;    // 해당 칸이 자기자신의 몸으로 바뀜
                    Snack tail = deque.pollLast();    // 몸 길이를 줄이기
                    board[tail.r][tail.c] = 0;        // 꼬리가 위치한 칸을 비워주기
                }
            }
        }
        
        System.out.println(second);        // 게임이 몇 초에 끝나는지 출력
    }
    
    public static Snack goStraight(int r, int c, int d) {
        Snack snack = null;
        
        switch (d) {
            case 0:
                // 앞으로 이동한 곳이 벽이 아니고, 자기자신의 몸도 아니라면 
                if (r - 1 >= 1 && board[r - 1][c] != 1) {
                    snack = new Snack(r - 1, c, d);        // 앞으로 이동한 뱀 객체 생성 
                }
                break;
            case 1:
                if (c + 1 <= N && board[r][c + 1] != 1) {
                    snack = new Snack(r, c + 1, d);
                }
                break;
            case 2:
                if (r + 1 <= N && board[r + 1][c] != 1) {
                    snack = new Snack(r + 1, c, d);
                }
                break;
            case 3:
                if (c - 1 >= 1 && board[r][c - 1] != 1) {
                    snack = new Snack(r, c - 1, d);
                }
                break;
        }
        
        return snack;    // 앞으로 이동한 뱀 객체 리턴
    }
}