[java][백준] 31863 - 내진 설계

문제

예제 입/출력

5 6
*.*...
..||..
..@*|*
.*.*..
..*##.

4 5

7 9
...#...#.
.*.*..*..
...*..#..
...**.*..
.*..*.@..
.#...**..
..#.#..*.

10 8

풀이

입력으로 지도가 주어지는데 지도에는 

• @: 진원지
• .: 일반 도로
• *: 내진 설계가 되어있지 않은 건물
• #: 내진 설계가 되어있는 건물
• |: 방파제

의 것들이 들어있다.

진원지는 상하좌우 각 방향으로 2의 충격을 줄 수 있고 그로 인해 무너진 건물들은 여진을 발생시키며 각 방향으로 1의 충격을 준다.

내진 설계가 이루어진 건물 같은 경우 두 번의 충격이 닿아야 무너지지만 내진 설계가 되어있지 않다면 바로 무너진다.

지진 방파제를 만나면 즉시 멈춘다.

제출 1 - 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 골드 5
 * 내진 설계
 * 사방으로 뻗어나가는 문제이기 때문에 BFS로 풀이
 */
public class No31863 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        //지도와 건물이 무너졌는지 지진이 몇번 방문했는지 체크 할 배열 초기화
        char[][] grid = new char[n][m];
        int[][] check = new int[n][m];
        //빌딩 개수와 무너진 건물 개수 넣을 변수 초기화
        int building = 0;
        int crash = 0;

        Deque<int[]> que = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                char chr = str.charAt(j);
                //진원지일 경우 -1(무너짐, 상관없음)으로 바꾸고 큐에 넣어줌
                if(chr == '@'){
                    check[i][j] = -1;
                    que.offer(new int[]{i, j, 2});
                }
                //빌딩 개수 세기
                if(chr == '*' || chr == '#') building++;
                grid[i][j] = chr;
            }
        }

        // 상 우 하 좌
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        /**
         * @: 진원지
         * .: 일반 도로
         * *: 내진 설계가 되어있지 않은 건물
         * #: 내진 설계가 되어있는 건물
         * |: 방파제
         */

        while(!que.isEmpty()){
            int[] earthquake = que.poll();
            int x = earthquake[0];
            int y = earthquake[1];
            int time = earthquake[2];
            for(int i=0;i<4;i++){
                //진원지일 경우 두번, 건물 무너짐 한번
                for(int j=1;j<=time;j++){
                    int nx = x + dx[i]*j;
                    int ny = y + dy[i]*j;
                    //지도를 벗어나거나 check가 -1일 경우 들어가지 않음
                    if(nx >= 0 && ny >= 0 && nx < n && ny < m
                            && check[nx][ny] != -1){
                        char chr = grid[nx][ny];
                        //방파제 만나면 더이상 진행하지 않음
                        if(chr == '|') break;
                        else if(chr == '*'){
                            //내진 x 건물 만나면 무너뜨리고 큐에 여진 넣어줌
                            check[nx][ny] = -1;
                            crash++;
                            que.offer(new int[]{nx,ny,1});
                        }else if(chr == '#'){
                            //내진 건물 만나면 몇번 왔었는지 체크하고 분기
                            if(check[nx][ny] == 1){
                                check[nx][ny] = -1;
                                crash++;
                                que.offer(new int[]{nx,ny,1});
                            }else{
                                check[nx][ny]++;
                            }
                        }else{
                            check[nx][ny] = -1;
                        }
                    }
                }
            }
        }

        System.out.println(crash + " " + (building-crash));
    }
}

 

특정지역에서 뻗어나가며 처리하는 문제기 때문에 BFS로 풀이했다.

큐에는 좌표와 충격의 강도를 같이 넣어줬고 check 배열을 만들어서 충격이 몇 번 닿았는지와 관련 없는(-1) 지역까지 체크해 줬다.

문제가 길긴 하지만 BFS만 안다면 충분히 풀 수 있는 문제였다고 생각한다.