문제 설명
문제 링크는 여기
https://www.acmicpc.net/problem/3190
어렸을 때 한 번쯤 해봤을 스네이크 게임 시뮬레이션을 구현하면 된다.
규칙을 정리하면 다음과 같다.
- N * N 크기의 맵
- 뱀은 맵의 최상단, 최우측에서 오른쪽 방향을 보며 시작
- 사과를 먹으면 뱀의 길이는 증가
- 벽이나 자신의 몸에 부딪히면 GAME OVER
- 입력 받은 초까지 이전 방향으로 전진, 이후 입력 받은 기호에 맞게 회전
접근
일단 벽에 부딪혔는지 확인하는 로직을 줄이기 위해 애초부터 맵의 크기를 (N+2)*(N+2)로 설정하고, 테두리에 값을 넣어주었다.
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
M = new int[N + 2][N + 2];
// 벽 생성
for (int i = 0; i < N + 2; i++) {
M[i][0] = 1;
M[0][i] = 1;
M[i][N + 1] = 1;
M[N + 1][i] = 1;
}이후 맵에 사과를 추가해주었다.
for (int k = 0; k < K; k++) {
int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
M[temp[0]][temp[1]] = 2;
}이제 뱀을 추가하면 된다. 나의 경우 뱀 객체를 새로 만들어서 사용하였다. 뱀 객체는 뱀의 한 마디를 의미한다. 이는 field로 해당 마디의 좌표값을 지니고 있다. 또한 LinkedList 형태이지만, 이후 내 풀이에서는 자신의 이전 객체에 대해서만 저장하면 되기 때문에 field로 pre를 갖도록 하였다.
class Snake {
public int x;
public int y;
public Snake pre;
public Snake() {
this(1, 1, null);
}
public Snake(int x, int y, Snake pre) {
this.x = x;
this.y = y;
this.pre = pre;
}
}이러한 뱀 객체를 main문에서 일단 추가해주었다.
head = new Snake();
tail = head;
// 뱀도 벽과 같이 부딪히면 안되므로 지도상 1로 표시되도록 함!
M[1][1] = 1;이후 게임을 시작한다.
// public static int[] dy = { 0, 1, 0, -1 };
// public static int[] dx = { 1, 0, -1, 0 };
// public static int d = 0;
int A = Integer.parseInt(br.readLine());
boolean alive = true;
// 본 게임 시작!
game: for (int a = 0; a < A; a++) {
String[] temp = br.readLine().split(" ");
int _time = Integer.parseInt(temp[0]);
// 이벤트 발생 전까지 기존 방향대로 전진
while (time < _time) {
time++;
alive = move();
if (!alive) {
break game;
}
}
// 방향 전환 이벤트
if (temp[1].equals("D"))
d = (d + 1) % 4;
else
d = (d + 3) % 4;
}
// 명령 끝난 이후에도 살아있다면 죽을 때까지 계속하기
while (alive) {
time++;
if (!move())
break;
}
// 최종적인 게임 시간 출력
System.out.println(time);move 메서드는 다음과 같다.
public static boolean move() {
int y = head.y + dy[d];
int x = head.x + dx[d];
// 벽 또는 몸통
if (M[y][x] == 1)
return false;
Snake temp = new Snake(x, y, null);
head.pre = temp;
head = temp;
// 그냥 길인 경우 이전 꼬리 부분을 삭제해줘야 길이가 맞음
if (M[y][x] == 0) {
M[tail.y][tail.x] = 0;
tail = tail.pre;
}
M[y][x] = 1;
return true;
}소스코드
최종적으로 제출한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static int N;
public static int K;
public static int[][] M;
public static Snake head;
public static Snake tail;
public static int[] dy = { 0, 1, 0, -1 };
public static int[] dx = { 1, 0, -1, 0 };
public static int d = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int time = 0;
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
M = new int[N + 2][N + 2];
for (int i = 0; i < N + 2; i++) {
M[i][0] = 1;
M[0][i] = 1;
M[i][N + 1] = 1;
M[N + 1][i] = 1;
}
for (int k = 0; k < K; k++) {
int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
M[temp[0]][temp[1]] = 2;
}
head = new Snake();
tail = head;
M[1][1] = 1;
int A = Integer.parseInt(br.readLine());
boolean alive = true;
game: for (int a = 0; a < A; a++) {
String[] temp = br.readLine().split(" ");
int _time = Integer.parseInt(temp[0]);
while (time < _time) {
time++;
alive = move();
if (!alive) {
break game;
}
}
if (temp[1].equals("D"))
d = (d + 1) % 4;
else
d = (d + 3) % 4;
}
while (alive) {
time++;
if (!move())
break;
}
System.out.println(time);
}
public static boolean move() {
int y = head.y + dy[d];
int x = head.x + dx[d];
if (M[y][x] == 1)
return false;
Snake temp = new Snake(x, y, null);
head.pre = temp;
head = temp;
if (M[y][x] == 0) {
M[tail.y][tail.x] = 0;
tail = tail.pre;
}
M[y][x] = 1;
return true;
}
}
class Snake {
public int x;
public int y;
public Snake pre;
public Snake() {
this(1, 1, null);
}
public Snake(int x, int y, Snake pre) {
this.x = x;
this.y = y;
this.pre = pre;
}
}결과
제출 결과는 다음과 같았다.
고찰
시작지점은 (0,0) 으로 준게 아니라 (1,1)으로 주길래 벽을 만들어서 구현해보니 입력 받는게 굉장히 편했던 것 같다.
풀고 나서 생각해보니 굳이 뱀 객체를 만들 필요없이 deque을 사용해도 충분히 할 수 있었을 것 같다는 생각이 들었다. 아니면 적어도 linked list를 활용하던지.
그런데 어쩌피 그런 자료 구조를 사용했어도 마디의 좌표값을 저장해야하므로 적어도 배열을 써야했기 때문에 큰 차이가 있을 것 같다는 생각은 들지 않았다.
파이썬 코드로는 시간이 훨씬 짧게 걸려서 이전엔 어떻게 짰을까하고 봤는데, 똑같이 뱀 객체를 만들어서 풀었다… 11달 전인데 예나 지금이나 난 똑같은 것 같다.
오엥