[BOJ] 3190 뱀 - JAVA

1. 문제

3190번: 뱀

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

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

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

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

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

---

2. 풀이

입력

뱀이 돌아다닐 공간은 가로 세로 모두 N+1씩 만들었다. 문제에서의 인덱스가 1부터 시작하기 때문이다.

뱀의 처음 위치를 입력(-1)하고, 사과 위치를 입력받으면서 사과라고 표시(1)한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(in.readLine());
int K = Integer.parseInt(in.readLine());
int[][] deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//우-하-좌-상(오른쪽 방향)

int[][] board = new int[N+1][N+1];
board[1][1] = -1;//뱀 처음 위치
for (int k = 0; k < K; k++) {
   st = new StringTokenizer(in.readLine());
   board[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
}

 

입력받은 초 만큼 이동

int nr, nc	다음 뱀 머리가 있을 곳
int d	뱀 머리가 향하는 방향
int time	걸린 시간

1.  덱에 뱀 처음 위치를 입력한다. 뱀 처음 위치에 -1(뱀)표시는 이미 위에서 해주었다.

2.  time+1부터 X초까지 정해진 방향으로 이동한다. 만약 이동 중에 벽이나 자신 몸에 부딪히면 x를 출력하고 끝낸다.

3.  만약 빈 공간이라면 길이를 원래대로 줄여야하므로 덱의 끝 위치를 뽑아서(꼬리) 그 공간을 0으로 만든다.

4.  뱀의 새 머리 위치를 -1로 만든다.

5.  덱의 맨 앞에 뱀 머리 위치를 추가한다.

6.  X초까지 모두 움직였다면 방향을 바꿔야한다. deltas를 오른쪽 방향으로 움직이게 저장했으므로 D라면 d+1, L이라면 d-1로 바꾼다. d-1을 했다가 인덱스에 벗어날 수 있으니 d+4-1=d+3을 한다. 인덱스 재조정을 위해 더한 값에 %4연산을 한다. 비슷한 방식을 이용한 문제는 [로봇청소기] 다.

7.  마지막으로, X초까지 모두 이동했으니 time을 X로 바꾼다.

int L = Integer.parseInt(in.readLine());
int nr, nc, d = 0, time = 0;

Deque<int[]> deque = new ArrayDeque<>();
deque.offerFirst(new int[]{1,1});

for (int l = 0; l < L; l++) {
   st = new StringTokenizer(in.readLine());
   int X = Integer.parseInt(st.nextToken());

   for (int x = time + 1; x <= X; x++) {
      nr = deque.peekFirst()[0] + deltas[d][0];
      nc = deque.peekFirst()[1] + deltas[d][1];
      if (nr <= 0 || nr > N || nc <= 0 || nc > N || board[nr][nc] == -1) {
         System.out.println(x);
         return;
      } else if (board[nr][nc] == 0) {//빈 공간
         board[deque.peekLast()[0]][deque.pollLast()[1]] = 0;//꼬리쪽 비우기
      }
      board[nr][nc] = -1;//새 머리 표시
      deque.offerFirst(new int[]{nr, nc});//뱀 머리 추가
   }

   //방향 바꾸기
   if (st.nextToken().charAt(0) == 'D') d = (d + 1) % 4;
   else d = (d + 3) % 4;

   time = X;
}

 

끝날때까지 이동

위의 코드와 유사하다. 그래서 함수로 뺄까 생각도 했었는데 그러려면 변수부터 static으로 옮기고 동작코드도 좀 수정해야해서 이대로 두었다.

방향바꾸는 부분이 없고 마지막에 time+1하는 부분이 다르다.

위에서는 x를 time+1부터 시작해서 반복이 될 때마다 x+1이 되었다. 그래서 부딪힐 때 그대로 x를 출력하는 게 가능했다.

지금은 부딪히지 않는 경우만 반복문 "안"에서 time+1을 해주기 때문에 부딪힌 시각은 더해지지 않는다. 따라서 마지막에 time+1(부딪힌 시각)을 한다.

while ((nr = deque.peekFirst()[0] + deltas[d][0]) > 0 && nr <= N && (nc = deque.peekFirst()[1] + deltas[d][1]) > 0 && nc <= N && board[nr][nc] != -1) {
   if (board[nr][nc] == 0) {//빈 공간
      board[deque.peekLast()[0]][deque.pollLast()[1]] = 0;//꼬리쪽 비우기
   }
   board[nr][nc] = -1;//새 머리 표시
   deque.offerFirst(new int[]{nr, nc});//뱀 머리 추가
   time++;
}

System.out.println(time+1);

---

3. 결과