[JAVA] 백준 3190 : 뱀

[JAVA] 백준 3190 : 뱀

문제

지도에 사과가 놓여있고, 뱀은 명령에 따라 정해진 방향으로 1초에 한 번 씩 움직인다. 뱀이 머리를 움직인 곳에 사과가 있으면 꼬리는 그대로 있으면서 몸의 길이가 늘어나고, 사과가 없으면 꼬리가 있는 칸은 비워줘야한다. 

• 뱀의 처음 몸길이는 1이다.

• 뱀의 처음위치는 (1,1)이다.

• 뱀의 처음 이동방향은 오른쪽이다.

• 사과는 먹고나면 없어진다.

• 명령은 L, D가 있으며 L은 왼쪽으로, D는 오른쪽으로 90도 방향을 트는 것을 말한다.

• 예를 들어 현재 방향이 오른쪽이면서 명령이 (3, D)라면, 3초까지 오른쪽으로 이동한 뒤에 4초부터 방향을 90도 틀어 아래로 움직인다.

접근방법

1. N x N 공간에서 벽을 설정해주기 위해 (N+2) x (N+2) 배열을 만든다.

2. 공간에서 빈칸은 0, 사과는 1, 벽은 2라고 정해놓고 벽을 따로 설정해준다.

// 벽 세팅
for(int i=0; i<N+2; i++)
    for(int j=0; j<N+2; j++)
        if(i==0 || j==0 || i==N+1 || j==N+1)
            map[i][j] = 2;

3. 명령어는 X초에 명령 'L' 혹은 'D'가 주어지므로 instruct[X] = 'L' 형식으로 저장한다. 시간을 인덱스로 사용하면 계속해서 경과시간을 나타내는 변수인 time이 증가할 때 참고하기 편하다.

// 명령어 저장
for(int i=0; i<L; i++)
    instruct[sc.nextInt()] = sc.next().charAt(0);

4. 뱀이 사과를 먹지 않으면 꼬리부터 없어지기 때문에 FIFO방식의 큐를 이용해 뱀의 몸을 저장한다. 뱀은 머리를 움직일 때 마다 머리가 있는 위치를 큐에 넣어주고, 뱀의 머리가 있는 장소에 사과가 있다면 큐에서 꼬리를 꺼내준다. 또한 뱀의 몸 어느 곳이라도 머리가 부딪히면 게임이 끝나도록 하기 위해 큐에 넣을 때에는 해당 공간을 벽과 동일한 2로 변경해준다. 꼬리를 poll() 할 때 역시 빈칸이 되도록 0으로 변경해준다.

5. 방향 전환은 로봇청소기(14503)과 같이 규칙을 이용한다.

private static int changeDir(int cur_dir, char instruct){
    int next_dir;
    if(instruct == 'D')
        next_dir = (cur_dir==3) ? 0 : ++cur_dir;
    else
        next_dir = (cur_dir==0)? 3 : --cur_dir;
​
    return next_dir;
}

- 즉, 북(↑) 동(→) 남(↓) 서(←)를 0 1 2 3 으로 정하고, 오른쪽으로 90도 꺾어져 이동할 때에는 1씩 증가하고, 왼쪽으로 꺾어질 때에는 1씩 감소하는 규칙을 이용한다. (효근짱!b)

6. 처리하는 순서는 다음과 같다. 1) 시간을 카운트한다. 2) 뱀의 머리 위치를 변경해주고 해당 위치를 큐에 넣는다. 3) 뱀의 머리 위치에 사과가 있는지 확인한다. - 사과가 있다면 아무일도 일어나지 않는다. - 사과가 없다면 큐를 poll() 해준다. 4) 해당 시간에 방g전환 명령이 있는지 확인한다. 명령이 있다면 방향을 바꿔준다.

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
​
public class Main{
​
    static int dr[] = {-1 ,0, 1, 0};
    static int dc[] = {0, 1, 0, -1};
​
    static class Pos{
        int r;
        int c;
        public Pos(int r, int c){this.r = r; this.c = c;}
    }
​
    private static int changeDir(int cur_dir, char instruct){
        int next_dir;
        if(instruct == 'D')
            next_dir = (cur_dir==3) ? 0 : ++cur_dir;
        else
            next_dir = (cur_dir==0)? 3 : --cur_dir;
​
        return next_dir;
    }
​
    private static Pos getNextPos(Pos pos, int dir){
        Pos next_pos = new Pos(pos.r, pos.c);
        switch (dir){
            case 0: --next_pos.r; break;
            case 1: ++next_pos.c; break;
            case 2: ++next_pos.r; break;
            case 3: --next_pos.c; break;
        }
        return next_pos;
    }
​
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
​
        int N = sc.nextInt();   // 보드 크기 (N x N)
        int K = sc.nextInt();   // 사과 개수
        int L;                  // 명령어 개수
        int time = 0;           // 시간초
        int dir = 1;            // 이동 방향 (북-0, 동-1, 남-2, 서-3)
​
        Queue<Pos> baam = new LinkedList<>();   // 뱀의 몸 좌표를 넣을 큐
        int map[][] = new int[N+2][N+2];        // 보드 (0-빈칸, 1-사과, 2-벽)
        char instruct[] = new char[100001];     // 명령
​
        // 벽 세팅
        for(int i=0; i<N+2; i++)
            for(int j=0; j<N+2; j++)
                if(i==0 || j==0 || i==N+1 || j==N+1)
                    map[i][j] = 2;
        // 사과 세팅
        for(int i=0; i<K; i++)
            map[sc.nextInt()][sc.nextInt()] = 1;
​
        L = sc.nextInt();
        // 명령어 저장
        for(int i=0; i<L; i++)
            instruct[sc.nextInt()] = sc.next().charAt(0);
​
        Pos cur_pos = new Pos(1, 1);
        baam.offer(cur_pos);
        map[cur_pos.r][cur_pos.c] = 2;
​
        while(true){
            ++time;
            // 뱀의 머리 위치 이동
            cur_pos.r += dr[dir];
            cur_pos.c += dc[dir];
            //cur_pos = getNextPos(cur_pos, dir);
​
            // 벽이나 뱀의 몸을 만났을 경우 게임 종료
            if(map[cur_pos.r][cur_pos.c] == 2 ){
                break;
            }
​
            // 빈칸인 경우 마지막 칸 꼬리를 비워줌
            if(map[cur_pos.r][cur_pos.c] == 0){
                Pos retail = baam.poll();
                map[retail.r][retail.c] = 0;
            }
            // 머리를 큐에 넣고 맵의 변수 변경
            baam.offer(cur_pos);
            map[cur_pos.r][cur_pos.c] = 2;
​
            // 방향전환
            if(instruct[time] == 'D' || instruct[time] == 'L')
                dir = changeDir(dir, instruct[time]);
        }
​
        System.out.println(time);
    }
}

- 예제 2번의 답을 계속 20이라고 생각했던 이유는 뱀이 1초때에 (1,1)에 있고, 2초때 (1,2)로 이동한다고 생각했기 때문. 뱀은 처음에 (1,1)에 있고 1초 때 (1,2)로 이동하므로 time을 0으로 초기화해줘서 해결 할 수 있었다(성희짱!b) - 시뮬레이션 문제는 특히 푸는데 시간이 많이 걸리는 것 같다. 풀이시간을 계속 줄여나갈 것!