[백준] JAVA - 16918. 봄버맨

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

16918번: 봄버맨

생각

처음엔 나머지 연산을 해서 폭탄위치 마킹 -> 빈곳에 폭탄 채우기 -> 폭탄위치가 마킹된곳 BFS로 폭발시키기 이런식으로 구현했는데 주기별로 위의 상태가 변화하는것이 아니라서 문제에서 요구하는것을 그대로 구현하도록 했습니다.

 

1. 폭탄이 설치된 위치를 큐에 넣어줍니다. (초기상태, 1초 후)

2. 빈곳에 폭탄을 채워넣습니다.

3. 1초 증가시켜줍니다. 만약 time이 주어진 N초와 같다면 리턴합니다.

4. bomb() -> 큐에 넣어있는 좌표들을 BFS를 통해 폭탄을 터뜨려줍니다.

5. 1초 증가시켜줍니다.

6. 1~5번을 time이 N보다 작을때까지 반복시켜줍니다.

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16918_봄버맨 {
	static int R,C,N;
	static char[][] map;
	static int dy[] = {1,-1,0,0};
	static int dx[] = {0,0,1,-1};
	static Queue<Pos> q;
	
	static class Pos{
		int y,x;

		public Pos(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		R = Integer.parseInt(st.nextToken()); // 세로
		C = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // N초
		
		map = new char[R][C];
		q = new LinkedList<Pos>();
		
		for (int i = 0; i < R; i++) {
			char[] temp = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = temp[j];
			}
		}
		
		solve();
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		System.out.println(sb);
		
		
	}
	private static void bomb() {
		List<Pos> bombList = new ArrayList<>();
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0){
				Pos now = q.poll();
				bombList.add(new Pos(now.y,now.x));
				for (int d = 0; d < 4; d++) {
					int ny = now.y + dy[d];
					int nx = now.x + dx[d];
					if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
					if(map[ny][nx] == 'O') {
						map[ny][nx] = '.';
					}
				}
			}
		}
		
		for (Pos pos : bombList) {
			map[pos.y][pos.x] = '.';
		}
		
	}
	
	private static void solve() {
		int time = 1;
		while(time < N) {
			//초기 설치된 폭탄 마크
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if(map[i][j] == 'O') {
						q.add(new Pos(i,j)); // 3초후에 터뜨릴 폭탄 마크
					}
				}
			}
			//빈곳에 폭탄 채워넣기
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if(map[i][j] == '.') {
						map[i][j] = 'O';
					}
				}
			}
			time++;
			if(time == N) return;
			
			//폭탄 터뜨리기
			bomb();
			
			time++;
		}
		
	}

}