Q. 1868 파핑파핑 지뢰찾기(D4)

문제

 

DFS와 BFS를 같이 이용해서 풀었다.

모든 방향을 다 생각해야 하므로

dy, dx는 현재 좌표를 제외한 모든 좌표를 순회할 수 있게 만들었다.

 

1. 처음 입력값을 받을 때 Queue에 폭탄들의 위치를 저장하고, 방문 처리를 했다.

2. 이후 저장된 폭탄들의 위치를 가지고, 폭탄이 없는 근처 칸들에 표시를 했다.

(Board[nextY][nextX]++, BFS 사용)

3. 폭탄이 근처에 있는 모든 칸에 표시가 완료됬다면, 이제 0을 체크할 차례이다.

0으로 표시 될 칸들과 이와 인접한 칸들이 한 번의 클릭에 연쇄적으로 숫자가 표기되므로

  1) 먼저 0인 칸을 방문했을 때 그 칸을 방문처리 하고(visited[y][x] = true) click_cnt++를 해준다.

  2) 이를 BFS를 이용해 만약 0인 칸 근처에 다른 0인 칸이 있을 경우 그 칸 근처에 대해 다시 BFS순회를 하고,

  3) 0이 아닌 칸의 경우 1)에서 클릭했던 한 번으로 연쇄적으로 칸이 보여지므로 방문 처리를 하면 된다.

4. 방문 처리가 안된 칸들이 있을 수 있으므로, 방문 처리가 안된 칸에 대해

    순회를 하며 이 칸들은 연쇄적으로 숫자가 표기되는 칸이 아니므로

    visited[y][x] = false일 경우 click_cnt++를 해준다.

5. 마지막으로 이후에 결과값인 click_cnt를 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {

    private static BufferedReader br;
    static int[][] Board;
    static boolean[][] Visited;
    static int[] dy = {1, 0, -1, 1, 0, -1, 1, -1};
    static int[] dx = {1, 1, 1, -1, -1, -1, 0, 0};
    static int N;
    static Queue<int[]> BombQueue;
    static int Click_Cnt;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
        BombQueue = new LinkedList<>();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            Board = new int[N][N];
            Visited = new boolean[N][N];
            Click_Cnt = 0;

            for (int i=0; i<N; i++) {
                char[] input = sc.next().toCharArray();
                for (int j=0; j<N; j++) {
                    if (input[j] == '*') {
                        BombQueue.add(new int[]{i, j});
                        Visited[i][j] = true;
                        Board[i][j] = -1;
                    }else {
                        Board[i][j] = 0;
                    }
                }
            }

            while (!BombQueue.isEmpty()) {
                int[] cur = BombQueue.poll();
                int curY = cur[0];
                int curX = cur[1];

                for (int i=0; i<8; i++) {
                    int nextY = curY + dy[i];
                    int nextX = curX + dx[i];
                    if (nextY > (N-1) || nextY < 0 || nextX > (N-1) || nextX < 0) continue;
                    if (Board[nextY][nextX] == -1) continue;
                    Board[nextY][nextX]++;
                }
            }

            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++) {
                    if (!Visited[i][j]) {
                        if (Board[i][j] == 0) {
                            if (!Visited[i][j]) {
                                Click_Cnt++;
                                dfs(i, j);
                            }
                        }
                    }
                }
            }

            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++) {
                    if (!Visited[i][j]) Click_Cnt++;
                }
            }

            System.out.printf("#%d %d\n", test_case, Click_Cnt);
        }
    }

    static void dfs(int y, int x) {
        Visited[y][x] = true;
        for (int i=0; i<8; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            if (nextY > (N - 1) || nextY < 0 || nextX > (N - 1) || nextX < 0) continue;
            if (Board[nextY][nextX] == 0 && !Visited[nextY][nextX]) {
                dfs(nextY, nextX);
            }else if (!Visited[nextY][nextX]) Visited[nextY][nextX] = true;
        }
    }
}