[알고리즘] 백준 16918 - 봄버맨

1. 문제

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

2. 입력

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

3. 풀이

1. 접근법

3초마다 폭탄이 터지기 때문에, 초마다 상태를 변경해주는 방식을 생각했다.
전체 상태를 저장할 배열에 각 지역의 상태를 저장하고 초마다 변경해준다.
상태는 폭탄이 터지기까지 남은 시간과 동일하게 설정했다.

• 상태
  - 4 : 폭탄이 없는 땅
  • 3 : 방금 막 폭탄을 설치 함(3초 남음)
  • 2,1 : 폭탄 터지기 까지 2,1초 남음
  • 0 : 지금 폭탄이 터져야 함(0초 남음)
• 주의점
  제일 처음 1초에 한해서만 아무것도 하지 않는다.
  나는 코드에서 제일 처음 1초(초기상태)는 없는 셈 치고 n-1 시간으로 계산했다.
  그렇기 때문에 처음 폭탄을 설치 할 때 3이 아니라 2인 상태로 넣어줘야 한다.(1초를 깎고 시작한 것이기 때문)
  다른 땅의의 경우 아직 폭탄을 설치하지 않았기 때문에 그대로 4를 넣어준다.

2. 그래프 탐색

그래프를 처음부터 순서대로 돌면서 현재 지역의 상태를 확인한다.
탐색을 시작하는 순간 먼저 1초를 깎아주고(초기상태를 넘기기 때문)
1초를 깎고 나서 확인한 현재 지역의 상태가 0이면(== 폭탄이 터질 차례면)
현재 지역 기준으로 상,하,좌,우를 같이 터트린다(=4로 만들어줌)

• 주의점
  폭탄이 터지는 범위안에 들어가는 지역이 폭탄을 가지고 있을 경우, 해당 폭탄도 터지면서 다른 범위에 영향을 주어야 하기 때문에 건드리지 않고 넘어가야 한다.

터트리고 나서 폭탄이 없는 땅(=4)으로 만들어준다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class bomberman_16918 {

    static int r,c,n;
    static int map[][];
    static int xdir[] = {1,-1,0,0};
    static int ydir[] = {0,0,1,-1};

    static boolean check[][];

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");

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

        map = new int[r][c];
        check = new boolean[r][c];


        char[] arr;

        for(int i=0;i<r;i++){
            arr = bf.readLine().toCharArray();
            for(int j=0;j<c;j++){
                if(arr[j]=='.'){
                    map[i][j] = 4;
                }
                else{
                    map[i][j] = 2;
                }
            }
        }

        //젤 처음 1초(초기상태)는 무시
        //n-1초 동안(처음 1초 제외)
        for(int i=0;i<n-1;i++){
            find();
        }

        //정답 출력
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                //4->아무것도 없는 지역이면
                if(map[i][j]==0 || map[i][j]==4){
                    System.out.print(".");
                }
                //2,3 -> 폭탄이 있는 지역
                else{
                    System.out.print("O");
                }
            }
            if(i!=r-1)
                System.out.println();
        }

    }


    //1초에 한번씩
    public static void find(){


        //.이면 4
        //3이 되면 폭탄 설치된거
        //0-> 지금 터져야함
        //터지고 나서 -> 4

        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                //전체 지역 1초씩 까줌
                if(!check[i][j])
                    map[i][j]--;

                if(map[i][j]<0){
                    map[i][j] = 4;
                }

                //폭탄 터질 차례면
                if(map[i][j]==0){
                    //상하좌우로 터트려줌
                    for(int k=0;k<4;k++){
                        int x = i+xdir[k];
                        int y = j+ydir[k];

                        //다른 폭탄이 안터트렸고 & 맵 범위 안일 때
                        if(x<r && y<c && x>-1 && y>-1 && !check[x][y]){
                            //터트리는 구역에 폭탄이 있어도
                            //그 폭탄도 터져야 하기 때문에 안바꿔주고 넘어감
                            if(x>i || y>j){
                                if(map[x][y]==1){
                                    continue;
                                }
                            }
                            //터트리고 아무것도 없는 상태로
                            map[x][y] = 4;
                            //터진 구역 표시
                            check[x][y] = true;
                        }
                    }
                    //터트리고 아무것도 없는 상태로
                    map[i][j]=4;
                }

            }

        }

        //1초 지날 때 마다 폭탄 터진 구역인지지 여부 초기화
        for(boolean a[]:check){
            Arrays.fill(a,false);
        }
/*
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
        System.out.println();
*/
    }
}