문제
봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.
폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.
봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.
- 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
- 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
- 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
- 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
- 3과 4를 반복한다.
폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.
예를 들어, 초기 상태가 아래와 같은 경우를 보자.
...
.O.
...1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.
OOO
OOO
OOO1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.
O.O
...
O.O풀이 도출
시간제한이 2초였고 R, C, N이 200보다 작았기 때문에 가장 최악의 경우 200 x 200 x 200 = 800만으로 충분히 모든 경우의 수를 체크할 수 있고 완전탐색 혹은 구현의 문제라고 생각해서 최대한 문제가 제시하는 것과 동일하게 문제를 해결하였다.
풀이
입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputStrs = br.readLine().split(" ");
int R = Integer.parseInt(inputStrs[0]); // R
int C = Integer.parseInt(inputStrs[1]); // C
int N = Integer.parseInt(inputStrs[2]); // 시간- BufferedReader를 통해서 입력의 오버헤드를 줄였다.
- 격자판의 크기와 게임이 진행될 시간(초)을 입력.
-
예시)
6 7 3 ....... ...O... ....O.. ....... OO..... OO.....
-
초기 폭탄 설치
- 초기에 폭탄을 설치할 때 폭탄 (
O)의 explosionTime을 3초로 지정
// 초기 폭탄 설치
for (int i = 0; i < R ; i++) {
String value = br.readLine();
for (int j = 0; j < value.length(); j++) {
A[i][j] = value.charAt(j);
if(A[i][j]=='O'){
explosionTime[i][j] = 3; // 폭탄이 터질 시간 (놓인 시간 + 3)
}
}
}봄버맨
- for문에서 time을 1초부터 시작해 N초만큼 동작을 반복.
- 만약 짝수 초일 경우 폭탄이 설치되어 있지 않는 모든 곳에 폭탄을 설치하고 그 폭탄의 시간은 현재 Time + 3을 해준다.
- 폭탄은 설치한 시간으로부터 3초 뒤에 터지기 때문에
- 홀수 초일 경우 explosionTime과 time이 같은 폭탄이 폭발한다
- 폭발하며 폭탄의 상하좌우에 현재 explosionTime과 time이 다른, 즉 현재 터질 시간이 아닌 폭탄의 경우 연쇄반응으로 터트린다.
- 만약 짝수 초일 경우 폭탄이 설치되어 있지 않는 모든 곳에 폭탄을 설치하고 그 폭탄의 시간은 현재 Time + 3을 해준다.
//
for(int time = 1; time < N+1; time++) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// 폭탄이 설치되있지 않은 모든 칸에 폭탄을 설치
if (time % 2 == 0) {
// 폭탄을 설치하고 터지는 시간 설정
if (A[i][j] != 'O') {
A[i][j] = 'O';
explosionTime[i][j] = time + 3;
}
} else {
// 시간이 다된 폭탄을 터트린다.
if (explosionTime[i][j] == time) {
A[i][j] = '.';
// 폭탄이 터지는 범위
for (int k = 0; k < 4; k++) {
int nextX = i + dx[k];
int nextY = j + dy[k];
// X, Y가 범위 내가 아니라면 coutinue;
if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C) {
continue;
}
// 터지는 범위에 폭탄이 있지만 폭탄이 터질 시간이 아니라면
if (A[nextX][nextY] == 'O' && explosionTime[nextX][nextY] != time) {
A[nextX][nextY] = '.';
explosionTime[nextX][nextY] = 0;
}
}
}
}
}
}
}출력
- StringBuilder를 사용해 격자판 상태 출력
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
sb.append(A[i][j]);
}
sb.append("\n");
}
System.out.println(sb);구현한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static char[][] A;
static int R, C, N;
static StringBuilder sb = new StringBuilder();
static int[][] explosionTime;
static int[] dx = {0, 1, 0, -1}; // 상, 하
static int[] dy = {1, 0, -1, 0}; // 좌, 우
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 한 줄에 여러 수를 공백으로 구분해서 입력받고 분할
String[] inputStrs = br.readLine().split(" ");
// 문자열 배열에서 정수 배열로 변환
int[] numbers = new int[inputStrs.length];
for (int i = 0; i < inputStrs.length; i++) {
numbers[i] = Integer.parseInt(inputStrs[i]);
}
R = numbers[0]; // R개의 줄
C = numbers[1]; // C개의 칸
N = numbers[2]; // N초
A = new char[R][C];
explosionTime= new int[R][C];
// 초기 폭탄 설치
for (int i = 0; i < R ; i++) {
String value = br.readLine();
for (int j = 0; j < value.length(); j++) {
A[i][j] = value.charAt(j);
if(A[i][j]=='O'){
explosionTime[i][j] = 3; // 폭탄이 터질 시간 (놓인 시간 + 3)
}
}
}
//
for(int time = 1; time < N+1; time++) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// 폭탄이 설치되있지 않은 모든 칸에 폭탄을 설치
if (time % 2 == 0) {
// 폭탄을 설치하고 터지는 시간 설정
if (A[i][j] != 'O') {
A[i][j] = 'O';
explosionTime[i][j] = time + 3;
}
} else {
// 시간이 다된 폭탄을 터트린다.
if (explosionTime[i][j] == time) {
A[i][j] = '.';
// 폭탄이 터지는 범위
for (int k = 0; k < 4; k++) {
int nextX = i + dx[k];
int nextY = j + dy[k];
// X, Y가 범위 내가 아니라면 coutinue;
if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C) {
continue;
}
// 터지는 범위에 폭탄이 있지만 폭탄이 터질 시간이 아니라면
if (A[nextX][nextY] == 'O' && explosionTime[nextX][nextY] != time) {
A[nextX][nextY] = '.';
explosionTime[nextX][nextY] = 0;
}
}
}
}
}
}
}
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
sb.append(A[i][j]);
}
sb.append("\n");
}
System.out.println(sb);
}
}결과
류세민님의 개발블로그 입니다