[백준_16918번] 봄버맨

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

16918번: 봄버맨

[문제]

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

 

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

 

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다. 예를 들어, 초기 상태가 아래와 같은 경우를 보자.

 

1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.

 

1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.

 

[입력 조건]

 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_16918 {
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	static int[][] boomtime; // 폭탄이 설치된 시간을 저장하는 변수(time 기준)
	static char[][] map;
	static int r,c,n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		n=sc.nextInt();
		
		map=new char[r][c];
		boomtime=new int[r][c];
		
		for(int i=0;i<r;i++) {
			String str=sc.next();
			for(int j=0;j<c;j++) {
				map[i][j]=str.charAt(j);
				
				// 처음 폭탄이 터져야 하는 시간은 시작 후 3초뒤
				if(map[i][j]=='O')
					boomtime[i][j]=3;
			}
		}
			
		int time=1; // 1초 동안 봄버맨은 아무것도 하지 않기 때문에 1로 초기화 후 시작
		while(time<n) {
			time++; // 시간 증가
			boomberman(time); // 봄버맨이 새로운 폭단을 설치하는 시간을 2초->4초->6초...
			if(time==n) break;
			
			time++;
			boom(time); // 폭탄이 터지는 시간은 3초->5초->7초...
			if(time==n) break;
		}
		
		printmap();
	}
	
	// 봄버맨이 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치하는 함수
	static void boomberman(int time) {
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(map[i][j]=='.') {
					map[i][j]='O';
					/*
					 * time시간에 설치된 폭탄은 3초 뒤에 폭발하기 때문에
					 * boomtime 배열에 time+3을 저장한다.
					 */
					boomtime[i][j]=time+3;
				}
			}
		}
	}
	
	// 폭탄이 터지는 함수
	static void boom(int time) {
		// 배열의 모든 칸을 탐색하면서 터져야하는 time 값을 갖는 위치를 찾는다.
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(boomtime[i][j]==time) {
					map[i][j]='.'; // 폭탄 위치 초기화
					// 상,하,좌,우 초기화
					for(int k=0;k<4;k++) {
						int nx=i+dx[k];
						int ny=j+dy[k];
						
						if(nx<0||ny<0||nx>=r||ny>=c)
							continue;
						
						map[nx][ny]='.';
					}
				}
			}
		}
	}
	
	// 맵 출력 함수
	static void printmap() {
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				System.out.print(map[i][j]+"");
			}
			System.out.println();
		}
	}
}

 

[고찰]

 이번 문제는 그래프 탐색 카테고리에 있었지만 그보다는 주어진 조건을 모두 구현하는 구현 문제에 가까웠던 것 같다. 이번 문제의 핵심은 폭탄이 터져야 하는 시간을 따로 저장하는 2차원 배열이 필요하다는 것이다. 폭탄은 설치된 시간으로부터 3초뒤 폭발하기 때문에 새로운 폭탄이 설치될 때 마다 현재 시간+3한 값을 저장해두고, 폭탄이 터지는 함수에서 터져야 하는 폭탄 시간에 맞는 좌표를 기준으로 상,하,좌,우의 배열 값을 변경해주면 된다. 

 즉, 처음에 봄버맨은 가만히 있기 때문에 time을 1로 초기화 한 상태에서 시작하면 봄버맨이 폭탄을 설치하는 시간은 2, 4, 6... 초로 늘어나고, 폭탄이 터져야 하는 시점은 3(처음 설치된 폭탄), 5(2초때 설치한 폭탄), 7(4초때 설치한 폭탄)... 초가 된다.