[백준] 16918번: 봄버맨

📝 문제

처음엔 꼭 Queue를 써야하나..? 라는 의문이 들었지만, 생각을 하면 할수록 Queue를 써야 문제를 쉽게 해결할 수 있을 거라는 감이 왔다.
그래서 폭탄을 설치한 후 1초가 지난 시점에서 3초 후에 터질 폭탄의 위치를 큐에 담았다.
처음에 출력 결과물이 답안과 달라서 디버그를 통해 그 원인을 찾아냈는데,
폭탄이 터질 때, 그 인접한 곳을 0으로 초기화하면서 같은 시점에 폭탄이 터질 곳까지 0으로 초기화하는 실수를 하는 바람에 출력결과가 달라졌다. 그 곳을 0으로 초기화하면 그 폭탄이 터지지 않는 것으로 계산되어 그 폭탄의 인접 부분은 초기화되지 않기 때문!

📌 코드

package Baekjoon;

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

public class BOJ16918 {

    static int r;//row
    static int c;//column
    static int n;//second
    static int[][] graph;

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        int[] moveX = {0, 0, -1, 1};
        int[] moveY = {-1, 1, 0, 0};

        Queue<int[]> q = new LinkedList<>();//폭탄을 설치할 곳을 담는다

        graph= new int[r][c];
        //처음 0초와 1초의 상태
        for(int i = 0; i < r; i++){
            String input = br.readLine();
            for(int j = 0; j < c; j++){
                char curInput = input.charAt(j);
                if(curInput == 'O'){
                    graph[i][j] = 3; //3초 후에 터진다
                } else {
                    graph[i][j] = 0; //현재 폭탄이 없다
                    q.add(new int[]{i, j});
                }
            }
        }
        int curN = 1;//현재 지난 시간
        while(curN < n){
            curN++;
            //빈 곳에 폭탄 설치
            while(!q.isEmpty()){
                int[] curPoint = q.poll();
                graph[curPoint[0]][curPoint[1]] = curN + 3;
            }
            //폭발
            for(int i = 0; i < r; i++){
                for(int j = 0; j < c; j++){
                    if(graph[i][j] == curN) {
                        graph[i][j] = 0;
                        q.add(new int[] {i,j});
                        for(int k = 0; k < 4; k++){
                            if(i+moveY[k] >= 0 && i+moveY[k] < r && j+moveX[k] >= 0 && j+moveX[k] < c){
                                if(graph[i+moveY[k]][j+moveX[k]] != curN){
                                    graph[i+moveY[k]][j+moveX[k]] = 0;
                                    q.add(new int[] {i+moveY[k], j+moveX[k]});
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(graph[i][j] == 0) System.out.print(".");
                else System.out.print("O");
            }
            System.out.println("");
        }
    }
}

좋은 웹페이지 즐겨찾기