[JAVA] 백준 3190번 뱀
문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
풀이과정
1. N을 입력받아, NxN 크기의 map을 만들어주고 K를 입력받아 K의 횟수만큼 for문을 반복하며 0으로 채워진 map에 사과( 1 ) 을 채워넣는다. 뱀은 2로 표현한다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
map[0][0] = 2;
K = Integer.parseInt(br.readLine());
for(int i=0; i<K; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int column = Integer.parseInt(st.nextToken());
map[row-1][column-1] = 1;
}
2. L을 입력받고 그 크기만큼 GET 노드 ( time, direction 을 가지고 있다. ) 를 가진 배열 ( gets ) 을 생성한다. 그리고 L의 횟수만큼 for문을 반복하며 gets 배열에 채워넣는다. [ max_time 은 시뮬레이션 과정의 반복횟수를 정하기 위해서 넣었다. for문의 마지막에 바뀐값이 방향전환이 되는 마지막 time인데, 그 time에 N 을 더해주면 시뮬레이션의 최대횟수가 된다. ]
L = Integer.parseInt(br.readLine());
gets = new GET[L];
for(int i=0; i<L; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char direction = (st.nextToken()).charAt(0);
gets[i] = new GET(time, direction);
max_time = time;
}
3. 동 (r) , 서 (l) , 남 (d) , 북 (u) 각 방향을 매 시뮬레이션 마다 정해놓고 진행한다. [ 주어진 문제에선 뱀이 오른쪽으로 출발을 하기때문에 시작 방향은 r 이 된다. ]
change_time 은 다음으로 방향 전환 할 시간, change_dir 은 그 시간에 방향전환 할 방향이다. [ D : 오른쪽, L : 왼쪽 ]
now_dir = 'r';
change_dir = gets[k].direction;
change_time = gets[k++].time;
4. deque 를 이용해 시뮬레이션을 진행한다. 시작점은 map[0][0] 이므로 노드 POS( y좌표, x좌표 를 가지고 있다. ) 0,0 을 deque에 넣고 시작한다.
Deque<POS> deque = new LinkedList<>();
deque.add(new POS(0, 0));
4_1. 시뮬레이션 과정에서 항상 시작할 땐 map 에서 사과를 제외하곤 0 으로 초기화 시켜준다.
for(int o=0; o<N; o++) {
for(int u=0; u<N; u++) {
if(map[o][u] == 2) {
map[o][u] = 0;
}
}
}
4_2. NxN map의 범위를 벗어날 경우 break, time 을 가져온다.
if(now_x + 1 >= N) {
result_time = i;
break;
}
4_3. 꼬리와 머리가 만나는 경우 break, time 을 가져온다.
if(deque.getFirst().y == deque.getLast().y && deque.getFirst().x == deque.getLast().x + 1 && deque.size() != 1) {
result_time = i;
break;
}
4_4. 다음 좌표가 사과 ( 1 ) 인 경우, 다음 좌표를 deque에 추가하고 while문을 통해서 deque가 가지고 있는 좌표들에 뱀 ( 2 ) 을 그려넣는다.
deque2 에는 해당 좌표들을 다시 넣어준다. [ 시뮬레이션의 마지막에 deque에 다시 이용하기 위해 임시저장 ]
if(map[now_y][next] == 1) {
deque.add(new POS(now_y, next));
now_x = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
4_5. 다음 좌표가 뱀의 몸통인 경우 break, time 을 가져온다.
else if(map[now_y][next] == 2) {
result_time = i;
break;
}
4_6. 다음 좌표가 빈 칸 ( 0 ) 인 경우, 다음 좌표를 deque에 추가하고 while문을 통해서 deque가 가지고 있는 좌표들에 뱀 ( 2 ) 을 그려넣는다. 단, 뱀을 그려넣는 과정중에 이미 다음 좌표가 2 라면 check에 true를 저장하고 break 를 통해 해당 반복문을 빠져나온다. [ 시뮬레이션의 마지막 과정에 check == true 인 경우 시뮬레이션을 break 걸고 time을 가져온다. ]
else if(map[now_y][next] == 0) {
deque.add(new POS(now_y, next));
deque.poll();
now_x = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
if(map[p.y][p.x] == 2) {
check = true;
break;
}
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}if(check == true) {
result_time = i;
break;
}
5. deque2 에 임시로 저장되어있던 좌표들을 반복문을 통해서 다시 deque에 저장한다.
while(!deque2.isEmpty()) {
POS p = deque2.poll();
deque.add(new POS(p.y, p.x));
}
6. 모든 시뮬레이션 과정을 마친 후에 현재 있는 time이 방향전환 할 time 이라면 방향 전환을 한다. [ now_dir 변경 ]
변경 후엔 gets 배열에 저장되어 있는 다음 값을 불러와 change_time, change_dir 을 변경한다.
if(i == change_time) {
if(change_dir == 'D') {
if(now_dir == 'r') {
now_dir = 'd';
}
else if(now_dir == 'l') {
now_dir = 'u';
}
else if(now_dir == 'u') {
now_dir = 'r';
}
else if(now_dir == 'd') {
now_dir = 'l';
}
}
if(change_dir == 'L') {
if(now_dir == 'r') {
now_dir = 'u';
}
else if(now_dir == 'l') {
now_dir = 'd';
}
else if(now_dir == 'u') {
now_dir = 'l';
}
else if(now_dir == 'd') {
now_dir = 'r';
}
}
change_dir = gets[k].direction;
change_time = gets[k].time;
if(k != L - 1) {
k++;
}
}
7. break를 통해서 나온 result_time을 출력한다.
Solution
import java.io.*;
import java.util.*;
public class BaekJoon_3190_뱀 {
public static class GET{
int time;
char direction;
public GET(int time, char direction) {
this.time = time;
this.direction = direction;
}
}
public static class POS{
int y;
int x;
public POS(int y, int x) {
this.y = y;
this.x = x;
}
}
public static int N, K, L, max_time, k, change_time, now_y, now_x, result_time;
public static char change_dir, now_dir;
public static int map[][];
public static GET gets[];
public static boolean check;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
map[0][0] = 2;
K = Integer.parseInt(br.readLine());
for(int i=0; i<K; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int column = Integer.parseInt(st.nextToken());
map[row-1][column-1] = 1;
}
L = Integer.parseInt(br.readLine());
gets = new GET[L];
for(int i=0; i<L; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char direction = (st.nextToken()).charAt(0);
gets[i] = new GET(time, direction);
max_time = time;
}
now_dir = 'r';
change_dir = gets[k].direction;
change_time = gets[k++].time;
Deque<POS> deque = new LinkedList<>();
deque.add(new POS(0, 0));
for(int i=1; i<=max_time+N; i++) {
Deque<POS> deque2 = new LinkedList<>();
for(int o=0; o<N; o++) {
for(int u=0; u<N; u++) {
if(map[o][u] == 2) {
map[o][u] = 0;
}
}
}
if(now_dir == 'r') {
if(now_x + 1 >= N) {
result_time = i;
break;
}
else {
int next = now_x + 1;
if(deque.getFirst().y == deque.getLast().y && deque.getFirst().x == deque.getLast().x + 1 && deque.size() != 1) {
result_time = i;
break;
}
if(map[now_y][next] == 1) {
deque.add(new POS(now_y, next));
now_x = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
else if(map[now_y][next] == 2) {
result_time = i;
break;
}
else if(map[now_y][next] == 0) {
deque.add(new POS(now_y, next));
deque.poll();
now_x = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
if(map[p.y][p.x] == 2) {
check = true;
break;
}
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
}
}
else if(now_dir == 'l') {
if(now_x - 1 < 0) {
result_time = i;
break;
}
else {
int next = now_x - 1;
if(deque.getFirst().y == deque.getLast().y && deque.getFirst().x == deque.getLast().x - 1 && deque.size() != 1) {
result_time = i;
break;
}
if(map[now_y][next] == 1) {
deque.add(new POS(now_y, next));
now_x = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
else if(map[now_y][next] == 2) {
result_time = i;
break;
}
else if(map[now_y][next] == 0) {
deque.add(new POS(now_y, next));
deque.poll();
now_x = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
if(map[p.y][p.x] == 2) {
check = true;
break;
}
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
}
}
else if(now_dir == 'd') {
if(now_y + 1 >= N) {
result_time = i;
break;
}
else {
int next = now_y + 1;
if(deque.getFirst().y == deque.getLast().y + 1 && deque.getFirst().x == deque.getLast().x && deque.size() != 1) {
result_time = i;
break;
}
if(map[next][now_x] == 1) {
deque.add(new POS(next, now_x));
now_y = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
else if(map[next][now_x] == 2) {
result_time = i;
break;
}
else if(map[next][now_x] == 0) {
deque.add(new POS(next, now_x));
deque.poll();
now_y = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
if(map[p.y][p.x] == 2) {
check = true;
break;
}
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
}
}
else if(now_dir == 'u') {
if(now_y - 1 < 0) {
result_time = i;
break;
}
else {
int next = now_y - 1;
if(deque.getFirst().y == deque.getLast().y - 1 && deque.getFirst().x == deque.getLast().x && deque.size() != 1) {
result_time = i;
break;
}
if(map[next][now_x] == 1) {
deque.add(new POS(next, now_x));
now_y = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
else if(map[next][now_x] == 2) {
result_time = i;
break;
}
else if(map[next][now_x] == 0) {
deque.add(new POS(next, now_x));
deque.poll();
now_y = next;
while(!deque.isEmpty()) {
POS p = deque.poll();
if(map[p.y][p.x] == 2) {
check = true;
break;
}
map[p.y][p.x] = 2;
deque2.add(new POS(p.y, p.x));
}
}
}
}
while(!deque2.isEmpty()) {
POS p = deque2.poll();
deque.add(new POS(p.y, p.x));
}
if(i == change_time) {
if(change_dir == 'D') {
if(now_dir == 'r') {
now_dir = 'd';
}
else if(now_dir == 'l') {
now_dir = 'u';
}
else if(now_dir == 'u') {
now_dir = 'r';
}
else if(now_dir == 'd') {
now_dir = 'l';
}
}
if(change_dir == 'L') {
if(now_dir == 'r') {
now_dir = 'u';
}
else if(now_dir == 'l') {
now_dir = 'd';
}
else if(now_dir == 'u') {
now_dir = 'l';
}
else if(now_dir == 'd') {
now_dir = 'r';
}
}
change_dir = gets[k].direction;
change_time = gets[k].time;
if(k != L - 1) {
k++;
}
}
if(check == true) {
result_time = i;
break;
}
}
System.out.println(result_time);
}
}