
https://www.acmicpc.net/problem/3190
문제분석
뱀띠로서 이 문제를 넘길 수 없었다.
어쩌면 유명하다고도 할 수 있는, 뱀 게임이라고 볼 수 있다. 근데 문제가 은근 쉽다. 방향을 바꾸는 부분을 다 알려주고, 이대로 게임했을 때 얼마만에 게임이 끝나냐! 라는 질문이다.
자료구조를 다양하게 쓰는 문제이다.
1. 사과의 위치
2. 꼬리 길이에 대한 queue
3. 꼬리가 어디에 위치해있는지에 대한 boolean 배열
4. 입력 배열
등등...
이 자료구조들을 이용해서, time 변수를 1씩 올리면서 해당 시간에 벌어지는 사건들을 정리하며 나아가면 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int K = Integer.parseInt(br.readLine());
boolean[][] appleArr = new boolean[N][N];
StringTokenizer st;
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
appleArr[x - 1][y - 1] = true;
}
int L = Integer.parseInt(br.readLine());
String[][] logArr = new String[L][2];
for (int i = 0; i < L; i++) {
st = new StringTokenizer(br.readLine(), " ");
logArr[i][0] = st.nextToken();
logArr[i][1] = st.nextToken();
}
// 오른쪽 → 아래 → 왼쪽 → 위 (시계방향)
int[] dR = { 0, 1, 0, -1 };
int[] dC = { 1, 0, -1, 0 };
int logIdx = 0;
int dIdx = 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
boolean[][] isSnake = new boolean[N][N];
int x = 0;
int y = 0;
int time = 0;
q.offer(new int[] { x, y });
isSnake[x][y] = true;
while (true) {
time++;
int nextX = x + dR[dIdx];
int nextY = y + dC[dIdx];
// 벽 충돌
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
System.out.println(time);
return;
}
boolean hasApple = appleArr[nextX][nextY];
// 자기 몸 충돌
if (isSnake[nextX][nextY]) {
System.out.println(time);
return;
}
// 사과 없으면 꼬리 제거
if (!hasApple) {
int[] tail = q.poll();
isSnake[tail[0]][tail[1]] = false;
}
// 머리 추가
q.offer(new int[] { nextX, nextY });
isSnake[nextX][nextY] = true;
x = nextX;
y = nextY;
if (hasApple) {
appleArr[nextX][nextY] = false;
}
// 이동 끝난 뒤 방향 전환
if (logIdx < L && Integer.parseInt(logArr[logIdx][0]) == time) {
if (logArr[logIdx][1].equals("L")) {
dIdx = (dIdx == 0) ? 3 : dIdx - 1;
} else {
dIdx = (dIdx == 3) ? 0 : dIdx + 1;
}
logIdx++;
}
}
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 7576 토마토 (0) | 2026.02.19 |
|---|---|
| [JAVA] 백준 1717 집합의 표현 (0) | 2026.02.18 |
| [JAVA] 백준 17298 오큰수 (0) | 2026.02.16 |
| [JAVA] 백준 1987 알파벳 (0) | 2026.02.16 |
| [JAVA] 백준 1107 리모컨 (0) | 2026.02.15 |