Baekjoon 3190 뱀 - Deque

더 깔끔한 노션을 원한다

Baekjoon 3190 뱀 - Deque

3190번: 뱀

설계

1. 보드에 사과의 위치(좌표) 값을 1로 둔다.

2. 뱀의 위치는 2로 둔다.

3. 뱀의 방향 변환 정보는 Queue에 저장한다.

4. 뱀의 이동한 경로는 Deque에 저장한다. (크기는 사과를 먹을 때마다 1씩 증가, 초기값은 1)

1. 상수

상수가 총 3개로 구성하였다.

final int NORMAL = 0;
final int APPLE = 1;
final int SNAKE = 2;

NORMAL은 아무것도 아닌 곳이고, APPLE은 사과가 있는 위치, SNAKE는 뱀이 있는 위치이다.

2. 뱀의 방향 전환 정보를 queue에 저장한다.

방향 정보가 시간에 오름차순으로 되어 있기 때문에 바로 저장해주면 된다.

Queue<Turn> queue = new LinkedList<>();
for (int i = 0; i < L; i++) {
  st = new StringTokenizer(br.readLine());
  int time = Integer.parseInt(st.nextToken());
  char turn = st.nextToken().charAt(0);
  queue.add(new Turn(time, turn));
}

private class Turn {
  int time;
  char turn;

  Turn(int time, char turn) {
    this.time = time;
    this.turn = turn;
  }
}

Turn Class는 time(시간)과 turn(D or L)로 구성되어 있다.

3. 뱀의 이동한 경로는 Deque에 저장

Deque<Point> deque = new LinkedList<>(); // 뱀의 경로
deque.addLast(new Point(1, 1));
board[1][1] = 2;
int dequeSize = 1;
while (true) {
  time++;
  Point now = deque.peekFirst();
  Point next = new Point(now.y + dy[d], now.x + dx[d]);
  deque.addFirst(next);
  // [3-1] 
  if (isLimit(next) || board[next.y][next.x] == SNAKE) {
    break;
  }
  if (board[next.y][next.x] == APPLE) { // [3-2]
    dequeSize++;
  }
  board[next.y][next.x] = SNAKE;
  // [3-3]
  if (deque.size() > dequeSize) {
    Point point = deque.pollLast();
    board[point.y][point.x] = NORMAL;
  }
  ...
}

[3-1]

벽에 부딪히거나 자기 자신(뱀)에 부딪히는 경우 끝나게 된다.

[3-2]

사과를 만나게 되면 뱀의 길이(dequeSize)를 늘려준다.

[3-3]

뱀의 길이가 변함이 없다면 마지막에 deque에 들어온 원소(deque.pollLast())를 NORMAL로 바꿔준다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    Baekjoon solution = new Baekjoon();
    System.out.println(solution.P3190());
  }
}

class Baekjoon {
  final int NORMAL = 0;
  final int APPLE = 1;
  final int SNAKE = 2;
  int[] dy = { 0, 1, 0, -1 };
  int[] dx = { 1, 0, -1, 0 };
  int N;

  public int P3190() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int d = 0; // 처음에는 오른쪽(동)으로 가므로 초기값을 0으로 설정
    N = Integer.parseInt(br.readLine());
    int[][] board = new int[N + 1][N + 1];
    int K = Integer.parseInt(br.readLine()); // 사과의 개수
    for (int i = 0; i < K; i++) {
      st = new StringTokenizer(br.readLine());
      int y = Integer.parseInt(st.nextToken());
      int x = Integer.parseInt(st.nextToken());
      board[y][x] = APPLE; // 사과의 위치
    }
    int L = Integer.parseInt(br.readLine());
    Queue<Turn> queue = new LinkedList<>();
    for (int i = 0; i < L; i++) {
      st = new StringTokenizer(br.readLine());
      int time = Integer.parseInt(st.nextToken());
      char turn = st.nextToken().charAt(0);
      queue.add(new Turn(time, turn));
    }

    Deque<Point> deque = new LinkedList<>(); // 뱀의 경로
    deque.addLast(new Point(1, 1));
    board[1][1] = SNAKE;
    int dequeSize = 1;
    int time = 0;
    while (true) {
      time++;
      Point now = deque.peekFirst();
      Point next = new Point(now.y + dy[d], now.x + dx[d]);
      deque.addFirst(next);
      if (isLimit(next) || board[next.y][next.x] == SNAKE) { // 벽에 부딪히거나 자기 자신(뱀)에 부딪히는 경우 끝
        break;
      }
      if (board[next.y][next.x] == APPLE) {
        dequeSize++;
      }
      board[next.y][next.x] = SNAKE;
      if (deque.size() > dequeSize) {
        Point point = deque.pollLast();
        board[point.y][point.x] = NORMAL;
      }
      if (!queue.isEmpty() && queue.peek().time == time) {
        if (queue.poll().turn == 'D') { // 오른쪽으로 90도
          d = (d + 1) % 4;
        } else { // 왼쪽으로 90도
          d -= 1;
          if (d < 0) {
            d = 3;
          }
        }
      }
    }
    return time;
  }

  private boolean isLimit(Point next) {
    return next.x > N || next.y > N || next.x <= 0 || next.y <= 0;
  }

  private class Point {
    int y;
    int x;

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

  private class Turn {
    int time;
    char turn;

    Turn(int time, char turn) {
      this.time = time;
      this.turn = turn;
    }
  }
}