[백준] 16918 봄버맨 - BFS

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

16918번: 봄버맨

 

 

문제풀이

BFS 문제입니다.

문제를 구현하는데 있어서 제가 헷갈렸었던 점은,

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

이 조건들이었습니다.

 

여기서 

0초 일떄 : 아무일이 일어나지 않는다. (기본 초기값만 세팅)

1초 일떄 : 아무일도 일어나지 않는다.

2초 일때 : 먼저, 이전에 설치된 폭탄들의 위치를 Queue에 넣습니다. 그 이후에 폭탄이 설치되어있지 않은 모든 칸에 폭탄을 설치합니다.

3초 일떄 : 0초의 초기값들을 가지고서 (2초)일떄 Queue에 넣었던 값들을 BFS를 통해 폭발시킵니다.

4초 일때 : 먼저, 이전에 설치된 폭탄들의 위치를 Queue에 넣습니다. 그 이후에 폭탄이 설치되어있지 않은 모든 칸에 폭탄을 설치합니다.

5초 일떄 : 4초의 초기값들을 가지고서 (4초)일떄 Queue에 넣었던 값들을 BFS를 통해 폭발시킵니다.

...

...

..

 

 

여기서 보면 문제의 5번 조건에

3과 4를 반복한다고 나와있습니다.

해당 조건을 완벽히 이해하지 못하고서 진행하여 

time = 0, time = 1초 일때부터 작업을 시작하여 시간이 소요되었습니다.

 

5번 조건을 잘 이해하지 못하고 진행하여

처음에 time = 0 초, 즉 0초부터 N초까지 작업을 진행했기에 0초, 1초 일떄의 조건을 수행하면서 오답이 나왔었습니다.

즉, 2초부터 작업이 시작되어야합니다.

 

또, 문제에서 시간이 짝수(time%2==0)라면, 이전 폭탄의 위치를 먼저 Queue에 저장하고, 전체 배열을 'O'로 초기화시키는것.

홀수(time%2==1)일때는 이전에 저장된 Queue의 폭탄값들을 모두 BFS로 터뜨린다는 점이 헷갈렸었습니다.

 

 

 

문제코드

import java.util.*;

public class Main {
	
	public static int R, C, N;
	public static char[][] map;
	public static int time=0;
	public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	R = sc.nextInt();
    	C = sc.nextInt();
    	N = sc.nextInt();
    	map = new char[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);
    		}
    	}
    	
    	//0초 : 봄버맨 초기값.
    	//1초 : 1초동안 아무것도 안하므로 time = 2초부터 시작해야한다.
    	
    	//2초 : 폭탄설치되어있지 않은칸에 작업시작.
    	
    	//2초부터 N초까지 작업이 시작된다.
    	for(int time=2; time<=N;time++) {
    		
    		//시간이 짝수라면. 폭탄을 터뜨려야한다.
    		if( time % 2 == 0) {
    			for(int i=0;i<R;i++) {
    				for(int j=0;j<C;j++) {
    					if(map[i][j] == 'O') {
    						q.offer(new Node(i, j));
    					}
    				}
    			}
    			
    			//1초후의 값이 저장됨.
    			for(int i=0;i<R;i++) {
    				for(int j=0;j<C;j++) {
    					map[i][j] = 'O';
    				}
    			}
    			
    		}
    		
    		//시간이 홀수라면. 폭탄이 설치되어있지않은 모든 칸에 폭탄을 설치합니다.
    		if( time%2 == 1) { 			
    			BFS();
    		}
    	}
    	
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
    	
    }
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.r;
    		int y = temp.c;
    		map[x][y] = '.';
    		
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    			
    			map[nx][ny] = '.';
    		}
    	}
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}