들어가며
https://www.acmicpc.net/problem/3190
크기가 1인 뱀이 왼쪽위부터 움직이기 시작하며, 사과를 먹으며 크기가 커진다. 입력으로는 사과의 위치가 주어지고 사용자가 몇초에 어디로 회전할지에 대한 정보가 주어진다.
뭔가 어렸을 때 이와 비슷한 게임을 해본적이 있는 것 같다. 벽이나 자기몸에 부딫히면 Game Over이므로 사용자가 매번 어디로 이동할지를 누르는게 중요했던 것 같다. 다행히도 입력까지 우리가 넣는 것은 아니고 어떻게 움직일지 입력이 주어진다. 이에 따라 게임이 몇 초에 끝나는지만 출력하면 되는 시뮬레이션 문제이다.
본문으로
뱀은 사과를 먹으면 머리만 늘어나고, 사과가 없는 곳에 턴을 썻다면 머리가 늘어나고 꼬리를 줄어든다. 즉 처음과 끝만 신경써주면 되므로 자연스럽게 Deque 자료구조를 활용해서 풀었다.
public class Main {
static int[] dy = {0, 1, 0, -1};
static int[] dx = {1, 0, -1, 0};
static int N, K, L, ret, sDir;
static int[][] maps;
static ArrayDeque<Node> snake;
static ArrayDeque<Order> orders;
static class Node {
int y;
int x;
Node(int y, int x) {
this.y = y;
this.x = x;
}
}
static class Order {
int time;
char dir;
Order(int time, char dir) {
this.time = time;
this.dir = dir;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
maps = new int[N][N];
for (int i = 0; i < K; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
maps[y - 1][x - 1] = 1;
}
L = Integer.parseInt(br.readLine());
snake = new ArrayDeque<>();
orders = new ArrayDeque<>();
for (int i = 0; i < L; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char dir = st.nextToken().charAt(0);
orders.addLast(new Order(time, dir));
}
ret = 0;
sDir = 0;
snake.addLast(new Node(0, 0));
while (true) {
ret++;
// 가기전에 벽이거나 자기 몸이면 game over
Node head = snake.peekFirst();
int ny = head.y + dy[sDir];
int nx = head.x + dx[sDir];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) {
break;
}
ArrayDeque<Node> tempQ = new ArrayDeque<>();
boolean isSnake = false;
while (!snake.isEmpty()) {
Node body = snake.pollFirst();
if (body.y == ny && body.x == nx) {
isSnake = true;
break;
}
tempQ.addLast(body);
}
if (isSnake) {
break;
}
snake = tempQ;
// 사과가 있으면 머리만 증가, 없으면 머리 증가 후 꼬리 감소
if (maps[ny][nx] == 0) {
snake.addFirst(new Node(ny, nx));
snake.pollLast();
} else {
snake.addFirst(new Node(ny, nx));
maps[ny][nx] = 0;
}
// 다음 방향을 잡기 위해 방향 확인
if (!orders.isEmpty()) {
if (orders.peekFirst().time == ret) {
Order order = orders.pollFirst();
if (order.dir == 'L') {
sDir += 3;
sDir %= 4;
} else { // R
sDir += 1;
sDir %= 4;
}
}
}
}
System.out.println(ret);
}
}
코드는 시뮬레이션 문제치고는 그렇게 길지 않다. 하지만 문제에서 뱀의 시작위치가 가장 왼쪽 맨 위라고 표현하며 (1,1)을 알려준 것을 못보고 주어지는 사과의 위치들을 -1 하지 않고 그대로 받아버리는 바람에 인덱스 오류가 났다... 지나고 보면 정말 별 거 아니지만 초반 설계와 관련된거라 찾는데 무려 30분이나 걸렸다 ㅎㅎㅎㅎㅎ. 다음번에는 0부터 시작하는지, 1부터 시작하는지 꼭 잘보자!!!!
그리고 지금은 뱀이 자신의 몸에 부딫히는 것을 tempQ를 선언해서 Deque를 모조리 왔다갔다 하고 있는데,, 이는 자신의 몸인지 확인할 때마다 O(N)을 매번 소모하고 있는 것이기에 별로다. 그래서 아래와 같이 방문 배열을 활용해서 Deque의 Last부분만 방문 미처리해주면 되므로 시간복잡도를 확 줄였다.
public class Main {
static int[] dy = {0, 1, 0, -1};
static int[] dx = {1, 0, -1, 0};
static int N, K, L, ret, sDir;
static int[][] maps, visited;
static ArrayDeque<Node> snake;
static ArrayDeque<Order> orders;
static class Node {
int y;
int x;
Node(int y, int x) {
this.y = y;
this.x = x;
}
}
static class Order {
int time;
char dir;
Order(int time, char dir) {
this.time = time;
this.dir = dir;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
maps = new int[N][N];
visited = new int[N][N];
for (int i = 0; i < K; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
maps[y - 1][x - 1] = 1;
}
L = Integer.parseInt(br.readLine());
snake = new ArrayDeque<>();
orders = new ArrayDeque<>();
for (int i = 0; i < L; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char dir = st.nextToken().charAt(0);
orders.addLast(new Order(time, dir));
}
ret = 0;
sDir = 0;
snake.addLast(new Node(0, 0));
visited[0][0] = 1;
while (true) {
ret++;
// 가기전에 벽이거나 자기 몸이면 game over
Node head = snake.peekFirst();
int ny = head.y + dy[sDir];
int nx = head.x + dx[sDir];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] != 0) {
break;
}
// 사과가 있으면 머리만 증가, 없으면 머리 증가 후 꼬리 감소
snake.addFirst(new Node(ny, nx));
visited[ny][nx] = 1;
if (maps[ny][nx] == 0) {
Node tail = snake.pollLast();
visited[tail.y][tail.x] = 0;
} else {
maps[ny][nx] = 0;
}
// 다음 방향을 잡기 위해 방향 확인
if (!orders.isEmpty()) {
if (orders.peekFirst().time == ret) {
Order order = orders.pollFirst();
if (order.dir == 'L') {
sDir += 3;
sDir %= 4;
} else { // R
sDir += 1;
sDir %= 4;
}
}
}
}
System.out.println(ret);
}
}마무리하며
요즘 시뮬레이션 문제를 자주 풀어보는데, 정말 초반 설계가 중요함을 자주 느낀다. 생각을 코드로 옮기는 연습이 잘 된다는 점에서 시뮬레이션 문제는 정말 재밌지만, 초반에 실패하면 그 정말 많은 시간을 잡아먹는다... 코테에서 이러면 끝장이다!!!
앞으로 조금 더 치밀하게 설계를 하고 문제 풀이에 들어가야겠다. 파이팅 🔥