https://www.acmicpc.net/problem/3190
뱀
잡설
대부분의 사람들이 한번씩은 해본 게임일 것 같다. 화면에 랜덤하게 나타나는 사과를 먹고 뱀의 몸 길이가 증가하다가 벽 혹은 자기 몸이랑 부딪히면 끝나는 게임.
대학 입학했을 때 프로그래밍 입문으로 만들어본 적 있었다.
그걸 다시 하려니 많이 헤멨던 것 같다.
풀이 과정
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
문제에서 친절하게 규칙이 나와있기때문에 규칙들을 어떻게 표현할지만 정하면 된다.
사과는 1, 뱀은 2로 정했다.
뱀은 길이가 계속 증가하고 뱀이 차지하고 있는 영역들의 좌표를 알아야 하기때문에 ArrayList로 저장했다.(사실 큐나 덱같은 다른 선형 자료구조를 써도 상관이 없을 것 같다.)
벽 혹은 자신의 몸에 부딪힐 때까지 반복하면서 시간을 재야 하기때문에 while(true)로 무한정 반복하면서 충돌판정을 한다.
그 다음은 회전에 대한 문제인데 회전을 이동하기 전에 방향 전환을 시키면 예제 통과를 못하는 것으로 보아 이동을 하고 방향 전환을 시키는게 맞았다.
풀이를 하며 가장 문제가 되었던 것은 뱀의 이동인데 뱀의 길이가 짧다면 큰 문제가 아니었지만 뱀이 길이가 길어질 수록 이상한 버그가 발생해 고치는데 애먹었다.
결국 효율적이지 못하지만 일단 가능하게 코드를 작성했고 답을 구했다.
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
static int[] dy = {1, -1, 0, 0, 1, 1, -1, -1};
static boolean visit[][];
static int n, m, k;
static int graph[][];
static int land[][];
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String first = br.readLine();
n = Integer.parseInt(first);
graph = new int[n + 1][n + 1];
String K = br.readLine();
k = Integer.parseInt(K);
for (int i = 0; i < k; i++) {
String[] line = br.readLine().split(" ");
// 그래프에서 사과의 값은 1
graph[Integer.parseInt(line[0])][Integer.parseInt(line[1])] = 1;
}
Queue<Operation> oper = new LinkedList<>();
String L = br.readLine();
int l = Integer.parseInt(L);
for (int i = 0; i < l; i++) {
String[] line = br.readLine().split(" ");
Operation op = new Operation(Integer.parseInt(line[0]), line[1]);
oper.add(op);
}
ArrayList<Pair> snake = new ArrayList<>();
// 뱀은 2
graph[1][1] = 2;
snake.add(new Pair(1, 1));
int timeCnt = 0;
Direction dir = Direction.RIGHT;
String rot;
while (true) {
timeCnt++;
Pair head = snake.get(0);
if (checkFin(head.x, head.y, dir))
break;
if (dir == Direction.UP) {
int tmpX = head.x - 1;
int tmpY = head.y;
int tmp1, tmp2;
if (graph[head.x - 1][head.y] == 1) {
for (Pair p : snake) {
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
snake.add(new Pair(tmpX, tmpY));
} else {
for (Pair p : snake) {
graph[p.x][p.y] = 0;
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
}
}
if (dir == Direction.DOWN) {
int tmpX = head.x + 1;
int tmpY = head.y;
int tmp1, tmp2;
if (graph[head.x + 1][head.y] == 1) {
for (Pair p : snake) {
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
snake.add(new Pair(tmpX, tmpY));
} else {
for (Pair p : snake) {
graph[p.x][p.y] = 0;
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
}
}
if (dir == Direction.LEFT) {
int tmpX = head.x;
int tmpY = head.y - 1;
int tmp1, tmp2;
if (graph[head.x][head.y - 1] == 1) {
for (Pair p : snake) {
tmp2 = p.y;
tmp1 = p.x;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
snake.add(new Pair(tmpX, tmpY));
} else {
for (Pair p : snake) {
graph[p.x][p.y] = 0;
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
}
}
if (dir == Direction.RIGHT) {
int tmpX = head.x;
int tmpY = head.y + 1;
int tmp1, tmp2;
if (graph[head.x][head.y + 1] == 1) {
for (Pair p : snake) {
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
snake.add(new Pair(tmpX, tmpY));
} else {
for (Pair p : snake) {
graph[p.x][p.y] = 0;
tmp1 = p.x;
tmp2 = p.y;
p.x = tmpX;
p.y = tmpY;
tmpX = tmp1;
tmpY = tmp2;
graph[p.x][p.y] = 2;
}
}
}
if (!oper.isEmpty()) {
Operation op = oper.peek();
if (timeCnt == op.sec) {
rot = op.dir;
dir = rotate(dir, rot);
oper.poll();
}
}
}
bw.write(timeCnt + "\n");
br.close();
bw.close();
}
private static Direction rotate(Direction cur, String rot) {
if (rot.equals("L")) {
if (cur == Direction.LEFT) {
cur = Direction.DOWN;
} else if (cur == Direction.RIGHT) {
cur = Direction.UP;
} else if (cur == Direction.UP) {
cur = Direction.LEFT;
} else if (cur == Direction.DOWN) {
cur = Direction.RIGHT;
}
}
if (rot.equals("D")) {
if (cur == Direction.LEFT) {
cur = Direction.UP;
} else if (cur == Direction.RIGHT) {
cur = Direction.DOWN;
} else if (cur == Direction.UP) {
cur = Direction.RIGHT;
} else if (cur == Direction.DOWN) {
cur = Direction.LEFT;
}
}
return cur;
}
private static boolean checkFin(int x, int y, Direction dir) {
if (dir == Direction.LEFT) {
return y - 1 < 1 || graph[x][y - 1] == 2;
}
if (dir == Direction.RIGHT) {
return y + 1 > n || graph[x][y + 1] == 2;
}
if (dir == Direction.UP) {
return x - 1 < 1 || graph[x - 1][y] == 2;
}
if (dir == Direction.DOWN) {
return x + 1 > n || graph[x + 1][y] == 2;
} else
return true;
}
}
enum Direction {
LEFT, RIGHT, UP, DOWN
}
class Pair {
public int x;
public int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class Operation {
public int sec;
public String dir;
public Operation(int sec, String dir) {
this.sec = sec;
this.dir = dir;
}
}
개인용 공부한 것을 정리하는 블로그입니다.