문제
N x N 보드에서 뱀이 사과를 먹으며 이동한다. 벽이나 자기 자신에 부딪히면 게임이 끝날 때, 게임이 몇 초에 끝나는지 구하라.
입력
첫째 줄에 보드 크기 N (2 ≤ N ≤ 100), 사과 수 K, 사과 위치, 방향 변환 횟수 L, 각 변환 정보(시각, 방향)가 주어진다.
출력
게임이 끝나는 시간을 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 3 3 4 2 5 5 3 3 3 D 15 L 17 D | 9 |
풀이
Queue로 뱀의 몸통을 관리하며 매 초 이동을 시뮬레이션한다.
- 보드 외곽을 벽(1)으로, 사과를 2로 설정한다. 뱀의 몸통은 1로 표시한다
- 매 초 현재 방향으로 한 칸 이동한다
- 다음 칸이 벽이나 몸통(1)이면 게임 종료
- 사과(2)가 있으면 머리를 Queue에 추가하고 꼬리는 유지 (길이 증가)
- 빈 칸(0)이면 머리를 추가하고 꼬리를 Queue에서 제거하여 이동
- 현재 시각이 방향 변환 시각과 같으면 D(우회전) 또는 L(좌회전)으로 방향을 변경한다
핵심 아이디어: Queue의 FIFO 특성을 활용해 뱀의 머리는 뒤에 추가하고 꼬리는 앞에서 제거하면, 뱀의 이동과 성장을 자연스럽게 구현할 수 있다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day340BOJ3190뱀 {
static int N, K, L, ans = 0, idx = 1, jdx = 1, dir = 0, n = 0;
static int[] dr = { 0, 1, 0, -1 }, dc = { 1, 0, -1, 0 };
static int[][] map;
static String[][] cmd;
static Queue<int[]> q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
q = new LinkedList<>();
map = new int[N + 2][N + 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] = 1;
}
}
K = Integer.parseInt(br.readLine());
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 2;
}
L = Integer.parseInt(br.readLine());
cmd = new String[L][2];
for (int i = 0; i < L; i++) {
st = new StringTokenizer(br.readLine());
cmd[i][0] = st.nextToken();
cmd[i][1] = st.nextToken();
}
q.add(new int[] { idx, jdx });
map[idx][jdx] = 1;
while (true) {
int t = Integer.parseInt(cmd[n][0]);
char c = cmd[n][1].charAt(0);
ans++;
int nr = idx + dr[dir];
int nc = jdx + dc[dir];
if (map[nr][nc] == 1)
break;
else if (map[nr][nc] == 2) {
q.add(new int[] { nr, nc });
map[nr][nc] = 1;
} else if (map[nr][nc] == 0) {
q.add(new int[] { nr, nc });
int[] tmp = q.poll();
map[tmp[0]][tmp[1]] = 0;
}
idx = nr;
jdx = nc;
map[idx][jdx] = 1;
if (ans == t) {
if (c == 'D')
dir = (dir + 1) % 4;
else if (c == 'L')
dir = (dir + 3) % 4;
if (n + 1 < L)
n++;
}
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N²) (최대 N² 칸까지 이동 가능)
- 공간: O(N²)