[자바] 백준 3190 - 뱀 (java)

 문제 : boj3190

---

 

필요 알고리즘 개념

• 시뮬레이션
  
  • 문제에서 제시된대로 실제 뱀을 움직여보면서 언제 끝나는지 시뮬레이션을 돌려보면 된다.
• 덱 (deque) 등의 자료구조
  
  • 뱀의 머리부분이 움직이고, 꼬리부분이 사라지는 부분을 시뮬레이션으로 구현하기 위해 내가 생각한 가장 적합한 자료구조는 덱을 사용하는 것인데, 구현만 가능하다면 어떤 자료구조를 써도 당연히 상관없다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이하 풀이는 덱(deque)을 사용한다. 어떤건지 모른다면, 알고리즘 뿐 아니라 그냥 개발자를 한다면 필수로 알고 있어야하는 자료구조이므로 '자료구조 큐, 스택, 덱 (Queue, Stack, Deque)' 글을 참고해보자 (혹은 구글링!)

 

  로직을 말로 써보면 다음과 같다.

 

게임이 종료될때까지 이하를 계속 진행한다.

1-1. 시간을 증가시킨다.

1-2. 뱀 머리를 현재 방향에 따라 이동시킨다.

2. 이동한 곳이 맵의 밖이거나 뱀이면 현재까지 지난 시간을 출력하고 종료한다.

3-1. 사과가 있다면 사과를 없앤다.

3-2. 사과가 없다면 꼬리를 없앤다.

4. 뱀의 방향 변환 정보에 포함되는 경우 방향을 변경한다.

 

 

  문제에서 나온대로 위의 내용을 잘 구현해주면 된다. 그러니 풀이는 좀 더 쉽게 구현하는 방법을 다룬다. 

 

[ 1-2. 뱀 머리를 현재 방향에 따라 이동시킨다. / 4. 뱀의 방향 변환 정보에 포함되는 경우 방향을 변경한다.]

  내 경우 d가 방향을 나타내고 0이면 북쪽, 1이면 동쪽, 2면 남쪽, 3이면 서쪽을 나타낸다. 그럼 뱀의 방향 변환 정보가 'L'이라면 d--, 'D'라면 d++ 만 해주면 된다. 그리고 d의 범위는 [0, 3]이어야 하므로, 음수라면 4를 더해주고 d%=4 를 해주면 알아서 방향 변환이 가능하다.

  그리고 d에 따라 어느쪽으로 이동해야 할지는 상수로 지정해두었다.

private static final int[] DR = new int[] {-1, 0, 1, 0};
private static final int[] DC = new int[] {0, 1, 0, -1};

...

int nr = cur[0]+DR[d];	//위에 상수로 정해두고, d에 따라 움직이도록 했다.
int nc = cur[1]+DC[d];

...

d += dirChange[time];	//dirChange[time]에서 time은 X를 뜻한다. 
                        //'L'이라면 dirChange[X]=-1, 'D'면 1, 입력으로 안들어왔다면 0이다.
if (d<0) d+=4;
d%=4;

 

 

[ 2. 이동한 곳이 맵의 밖이거나 뱀이면 현재까지 지난 시간을 출력하고 종료한다. ]

  우선 맵의 밖인걸 확인하는건, 미리 보드의 크기를 가로세로 2칸씩 더 늘려두고, 외곽을 전부 맵의 밖이거나 뱀의 몸에 해당하는 위치를 나타내는 상수값으로 지정해둔다(코드에선 BLOCK이 해당 역할). 그럼 별도로 맵의 외곽인걸 체크하지 않아도 동일한 로직으로 뱀의 몸이거나 맵의 밖임을 확인할 수 있다.

int[][] map = new int[n+2][n+2];	// 미리 2칸 더 늘려둠
for (int[] row : map) Arrays.fill(row, BLOCK);	// 맵 전체를 BLOCK(뱀이거나 외곽임을 나타냄)으로 초기화
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map[i][j] = BLANK;
	// 실제 사용할 뱀이 이동할 공간을 BLANK(비어있음을 나타냄)로 초기화
    
...

int nr = cur[0]+DR[d];	// 다음 이동할 행
int nc = cur[1]+DC[d];	// 다음 이동할 열
if (map[nr][nc] == BLOCK) break;	// 이동할곳이 뱀이거나 맵 밖임을 한번에 체크

 

 

[ 1-2. 뱀 머리를 현재 방향에 따라 이동시킨다. / 3-2. 사과가 없다면 꼬리를 없앤다. ]

  머리부터 꼬리까지 순서대로 어느 칸에 뱀이 존재하는지 데이터를 모두 가지고 있다고 해보자. (이전까지 이동했던 길을 따라 꼬리가 계속 따라와야 하므로 순서대로 모든 위치를 저장해둘 수 밖에 없다.) 그렇다면 다음의 연산들이 필요하다.

 

  머리부분 데이터를 꺼내서 위치정보를 가져오고(A), 이동을 시킨 후 변경된 위치정보를 다시 저장하고(B), 꼬리의 데이터를 가져와 사과의 유무에 따라 없앨 수 있어야 한다(C).

 

  그럼 위 A, B, C연산을 효율적으로 할 수 있으면서, '순서'대로 머리부터 꼬리까지 각 칸의 정보를 가지고 있을 자료구조를 선택해야 한다. 난 덱(deque)을 선택했다. 순서도 있고, A,B,C 연산 모두를 O(1)에 처리 가능하다.

int[] cur = dq.peekLast();	// A
int nr = cur[0]+DR[d];
int nc = cur[1]+DC[d];
if (map[nr][nc] == BLOCK) break;

boolean isApple = map[nr][nc] == APPLE;
dq.addLast(pair(nr, nc));	// B
map[nr][nc] = BLOCK;
if (!isApple) {
    map[dq.peekFirst()[0]][dq.peekFirst()[1]] = BLANK;
    dq.pollFirst();	// C
}

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    private static final int BLOCK = -1;
    private static final int BLANK = 0;
    private static final int APPLE = 1;
    private static final int[] DR = new int[] {-1, 0, 1, 0};
    private static final int[] DC = new int[] {0, 1, 0, -1};
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private int[] pair(int r, int c) {
        return new int[] {r, c};
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n+2][n+2];
        for (int[] row : map) Arrays.fill(row, BLOCK);
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map[i][j] = BLANK;

        int k = Integer.parseInt(br.readLine());
        while (k-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = APPLE;
        }

        int[] dirChange = new int[10001];
        int l = Integer.parseInt(br.readLine());
        while (l-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            dirChange[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0)=='L'?-1:1;
        }

        int time = 0;
        Deque<int[]> dq = new ArrayDeque<>();
        dq.addLast(pair(1, 1));
        map[1][1] = BLOCK;
        int d = 1;
        while (true) {
            time++;
            int[] cur = dq.peekLast();
            int nr = cur[0]+DR[d];
            int nc = cur[1]+DC[d];
            if (map[nr][nc] == BLOCK) break;

            boolean isApple = map[nr][nc] == APPLE;
            dq.addLast(pair(nr, nc));
            map[nr][nc] = BLOCK;
            if (!isApple) {
                map[dq.peekFirst()[0]][dq.peekFirst()[1]] = BLANK;
                dq.pollFirst();
            }

            d += dirChange[time];
            if (d<0) d+=4;
            d%=4;
        }
        System.out.println(time);
    }
}