[Baekjoon] 백준 16919 봄버맨 2 (G4 / 구현) - Java

링크

https://www.acmicpc.net/problem/16919

16919번: 봄버맨 2

 

https://www.acmicpc.net/problem/16918

16918번: 봄버맨

봄버맨1은 실버 문제로 동일한 문제이지만 시간, 메모리 등의 조건이 다릅니다.

 

봄버맨2가 어렵다면 봄버맨1을 통해서 Solution을 찾고 다시 봄버맨 2를 푸시는 것을 추천드립니다.

 

 

 

 

문제 해석

- 입력
첫 번째 줄 : R C N  # R=높이 C=너비 N=흐른 시간
나머지 줄 : 지도 정보

 

- 출력

N초가 지난 후 지도 상태를 출력

 

- 문제 해석

폭탄은 놓인지 3초가 지난 후에 폭발하게됨

폭탄은 인접한 폭탄을 폭발시키며, 인접한 폭탄은 폭발하지 안하고 파괴됨

 

 

 

 

풀이 & 코드 해석

이 문제의 핵심은 폭탄이 폭발하는 경우와 파괴되는 경우를 잘 구분해야 한다는 점입니다.

 

3초 전에 설치된 폭탄은 폭발하지만, 그렇지 않은 폭탄의 경우 폭발 범위에 있더라도 폭발하지 않고 파괴된다는 차이가 있습니다.

 

- 순서 -
0초 : 초기 폭탄
1초 : 초기 폭탄 유지
2초 : 모두 폭탄으로 변경
3초 : 1초에 있던 폭탄 폭발 (1차 폭발)
4초 : 모두 폭탄으로 변경
5초 : 3초에 있던 폭탄 폭발 (2차 폭발)
6초 : 모두 폭탄으로 변경
7초 : 5초에 있던 폭탄 폭발 (1차 폭발)
...

 

추가적으로 폭발 순서를 잘 보고 규칙을 찾는 것이 중요합니다.

 

봄버맨 1의 경우 매 순서마다 지도를 갱신하여 출력해도 Solution을 찾는데 문제가 없지만, 봄버맨2는 시간과 메모리 조건이 더 까다롭기 떄문에 시간 초과 또는 메모리 초과가 일어날 수 있습니다.

 

위에 순서는 제가 임의로 폭발에 대한 순서를 정리해 놓은 것입니다.

 

 

문제에서 주어지는 예시 상태를 보면 마치 초기 상태에서 2번 폭발이 일어나면 원래 상태로 돌아가는 것 처럼 보입니다.

 

 

0 : 초기
.O
OO
---------
1 : 1차 폭발 결과
..
..
---------
2 : 2차 폭발 결과
OO
OO
---------
OO
OO
---------

하지만 위에 제가 임의로 작성한 테스트 케이스를 살펴보면 초기 상태는 왼쪽 위만 폭탄이 없는 상태였지만, 2번 폭발이 일어난 후 결과는 모두 폭탄을 가지는 상태로 변하는 것을 볼 수 있습니다.

 

따라서 폭탄의 상태는

1) 초기 상태
2) 1차 폭발 상태
3) 2차 폭발 상태
4) 모두 폭탄으로 가득 찬 상태

이렇게 4가지가 있다고 할 수 있습니다.

 

 

또한 이러한 상태들은

1초 == 1번
n%2 = 0라면 4번
n%4 == 1이라면 2번
n%4 == 3이라면 3번

들로 나눌 수 있습니다.

(제가 임의로 모두 찬 상태를 3번에 넣었을 뿐 다른 순서로 작성해도 무방합니다.)

 

 

위 상태들의 지도를 찾은 후 저장해두고 입력된 N에 맞은 지도를 출력해주면 문제를 해결할 수 있습니다.

 

 

코드

import java.io.*;
import java.util.*;

public class 봄버맨 {
	static char[][][] answer;
	static int R, C;

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	static Queue<Point> q;

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 첫 번째 줄
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		// 0 : 초기
		// 1 : 한 번 터진후 결과
		// 2 : 두 번 터진후 결과
		answer = new char[R][C][4];

		// 지도 초기화
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				for (int c = 1; c < 4; c++) {
					answer[i][j][c] = 'O';
				}
			}
		}

		// 나머지 줄
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			for (int j = 0; j < C; j++) {
				answer[i][j][0] = s.charAt(j);
			}
		}

//		print(answer, 0);

		for (int c = 0; c < 2; c++) {
			q = new LinkedList<>();
			for (int i = 0; i < answer.length; i++) {
				for (int j = 0; j < answer[i].length; j++) {
					if (answer[i][j][c] == 'O') {
						q.offer(new Point(i, j));
					}
				}
			}
			bfs(c + 1);
		}

//		print(answer,0);
//		System.out.println("---------");
//		print(answer,1);
//		System.out.println("---------");
//		print(answer,2);
//		System.out.println("---------");
//		print(answer,3);
//		System.out.println("---------");

		// 출력
		if (N == 1) {
			print(answer, 0);
		} else if (N % 2 == 0) {
			print(answer, 3);
		} else if (N % 4 == 3) {
			print(answer, 1);
		} else if (N % 4 == 1) {
			print(answer, 2);
		}

	}

	private static void bfs(int c) {
		while (!q.isEmpty()) {
			Point p = q.poll();
			answer[p.x][p.y][c] = '.';
			for (int d = 0; d < dx.length; d++) {
				int nx = p.x + dx[d];
				int ny = p.y + dy[d];

				if (nx >= 0 && nx < R && ny >= 0 && ny < C && answer[nx][ny][c] == 'O') {
					answer[nx][ny][c] = '.';
				}
			}
		}

	}

	private static void print(char[][][] answer, int idx) {
		for (int i = 0; i < answer.length; i++) {
			for (int j = 0; j < answer[i].length; j++) {
				System.out.print(answer[i][j][idx]);
			}
			System.out.println();
		}
	}
}

 

 

 

 

발생한 문제 & 해결 방안

출력을 위한 if문에서 1초일 때 다른 화면을 출력하여 75%에서 틀리는 현상이 발생하였다.

 

코드 작성 시 오타나 틀리는 일이 없도록 주의하기!!!!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java