[PS] 뱀(baekjoon 3190)

‘Dummy’ 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 ‘L’) 또는 오른쪽(C가 ‘D’)로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

해결 방법

문제에서 뱀은 이리저리 기어다니다가 사과를 먹는다면 몸의 길이를 1만큼 늘린다. 게임이 종료되는 조건은 벽에 부딫히거나 자기자신의 몸과 부딫히는 경우이다. 문제 해결을 위해 우리가 고려해야할 사항을 간단히 정리해보면 아래와 같다.

• 뱀의 이동방법
• 이동 방향 처리 방법
• 게임이 종료되는 조건
  • 벽에 부딫히는 경우 판별 방법
  • 자신의 몸에 부딫히는 경우 판별 방법

뱀의 이동방법

뱀의 이동방법을 이해하는것이 이 문제에서는 중요한 것 같다. 문제의 조건들을 보면 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 다음칸에 사과가 존재한다면 사과가 위치한 부분에 머리를 그대로 위치시키고 꼬리부분 또한 그대로 둔다(몸길이가 1만큼 늘어나는 효과). 사과가 없을경우에는 꼬리를 제거해주는 방법으로 처리해야하는것을 알 수 있다(몸길이 변화없음).

이동 방향 처리

예제입력 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

위에 예제입력1을 보면 7번째줄 부터 이동 방향에 대한 정보가 주어진다. 문제 본문에서 볼 수 있듯이 D는 오른쪽 90도 회전을 뜻하고 L은 왼쪽으로 90도 회전을 의미한다. “3 D” 는 3초 시점에서 뱀은 오른쪽으로 90도 회전해야한다는 뜻이된다. 필자의 경우 방향 처리를 위해 배열을 사용해서 아래와 같이 방향정보를 나타내었다.

static int[] dx = { 1, 0, -1, 0};	//동, 남, 서, 북
static int[] dy = { 0, 1, 0, -1};
...

그리고 방향 전환에 대한 정보를 다음과 같이 표현하였다.

동 → 0 남 → 1

서 → 2 북 → 3

그렇다면 오른쪽 90도 회전 왼쪽 90도 회전을 아래의 코드로 처리할 수 있다.

String c; //이곳에 방향 정보가 저장되었다 가정.

if(c.equals('L'))
	dir = dir == 0 ? (dir + 3) % 4 : (dir - 1) % 4; //왼쪽방향 90도 회전
else if(c.equals('D'))
	dir = (dir + 1) % 4; //오른쪽방향 90도 회전

게임 종료조건

벽에 부딫히는 경우 판별 방법

벽에 닿는 조건의 경우 단순히 게임의 map의 크기를 벗어나는지 체크만 해주면된다. 이 때 필자의 경우 문제에서 맨 좌측 가장 위쪽이 (1,1)이라는것에 착안하여 map[N+1][N+1]과 같이 정의해주었다. 이에 따라 경계검사를 해주면 될 것이다.

자신의 몸에 부딫히는 경우 판별 방법

본인은 뱀의 몸이 map에서 어디에 위치하는지를 저장하고 있는 queue를 정의했다. queue에 각 element가 마치 뱀의 몸 마디하나라고 생각해서 LinkedList snake라고 정의했다. 즉 뱀의 마디마디가 모여 뱀 한마리가 된것을 추상화했다고 생각하면 될 것이다ㅋㅋㅋ😄

아무튼 queue에 뱀의 위치정보를 이동이 발생할 때마다 갱신을 해준다. 최초에는 뱀의 머리 하나가 존재할 것 인데. (1, 1)에서 동쪽방향으로 처음 움직인다고 했으니 1초시점까지 queue에는 다음과 같은 연산이 발생한다. ( (1, 2)에 사과가 없다고 가정)

[1,1]→[1,2] (add [1,2])

[1,2] (remove [1,1])

왜냐하면 뱀은 우선 뱀의 머리를 다음칸에 위치시키고 사과가 없는 경우 꼬리를 제거한다고 했다.

그렇다면 (1, 2) 위치에 사과가 존재하는 경우라면 [1,1] → [1,2]가 되겠다. 이와 같은 연산을 보았을 때 FIFO형태를 띄고있으므로 queue를 이용한것이다. 이런식으로 뱀의 위치를 이동시마다 갱신시켜주면서 map에다가 뱀의 몸 정보 또한 갱신해준다.

map에 저장되는 정보로는 초기값 0, 사과 1, 자신의 몸 2로 두었다.

뱀이 몸의 길이를 늘려 머리를 다음위치로 이동할 때 다음위치를 토대로 map에다가 map[nextY][nextX] = 2와 같이 갱신해준다. 다음 위치에 사과가 존재한다면 별다른 처리를 해주지 않아도 되고 사과가 없다면 queue에서 꼬리를 제거해서 제거된 꼬리의 위치를 토대로 map에 다음과 같이 초기값으로 값을 설정해주어 맵에서 꼬리가 제거됨을 표시하는것이다. map[tailY][tailX] = 0 이런식으로 처리하다보면 자기 자신의 몸에 대한 정보가 map에 저장될 것이고 이 정보를 토대로 자기 자신의 몸에 부딫혔는지 검사를 할 수 있게된다(다음 이동 위치에 자기 자신의 몸이 존재하면 종료하는것이다).

코드

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

public class Main {

    static int map[][];
    static HashMap<Integer, Character> dirInfo = new HashMap<>();
    static LinkedList<SnakeBody> snake = new LinkedList<>();
    static int N;
    static int[] dx = { 1, 0, -1, 0};	//우, 하, 좌, 상
    static int[] dy = { 0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        map = new int[N+1][N+1];
        int numOfApple = Integer.parseInt(bf.readLine());

        StringTokenizer st;
        int x,y;

        for (int i = 0; i < numOfApple; i++) {
            st = new StringTokenizer(bf.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());

            map[y][x] = 1; // 1 == 사과
        }

        int numOfDirInfo = Integer.parseInt(bf.readLine());

        int t;
        Character dir;

        for (int i = 0; i < numOfDirInfo; i++) {
            st = new StringTokenizer(bf.readLine());

            t = Integer.parseInt(st.nextToken());
            dir = st.nextToken().charAt(0);

            dirInfo.put(t, dir);
        }

        snake.add(new SnakeBody(0, 0));
        int time = playGame(new SnakeBody(2, 1), 0);
        System.out.println(time);
    }

    static public int playGame(SnakeBody snakeHead, int dir) {
        int time = 1;

        while(true) {

            if((snakeHead.x <= 0 || snakeHead.x > N) || (snakeHead.y <= 0 || snakeHead.y > N)) {
                return time;
            }

            if (map[snakeHead.y][snakeHead.x] == 2) //자기 자신몸에 닿은경우
                return time;

            if (map[snakeHead.y][snakeHead.x] == 0) { //꼬리제거
                SnakeBody sb = snake.poll();
                map[sb.y][sb.x] = 0; //x,y에 대한 통일이 안됨.
            }

            snake.add(new SnakeBody(snakeHead.x, snakeHead.y));
            map[snakeHead.y][snakeHead.x] = 2;

            if(dirInfo.containsKey(time)) {
                Character c = dirInfo.remove(time);
                if(c.equals('L')) {
                    dir = dir == 0 ? (dir + 3) % 4 : (dir - 1) % 4;
                }
                else if(c.equals('D')) {
                    dir = (dir + 1) % 4;
                }
            }

            snakeHead.x = snakeHead.x + dx[dir];
            snakeHead.y = snakeHead.y + dy[dir];

            time++;
        }
    }

    static public class SnakeBody {
        int x;
        int y;

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