[SWEA/D4] 1868. 파핑파핑 지뢰찾기 - JAVA 자바

• 190ms
• 구현 BFS

최소의 클릭으로 지뢰를 제외한 모든 칸의 숫자들을 표시하는 문제이다. 핵심은 주변에 지뢰가 없는 칸은 8방향의 칸을 클릭없이 확인할 수 있다는 것이다. 즉, 클릭한 칸을 중심으로 가지가 뻗어나가는 구조로 BFS로 해결하였다.

 

먼저 주변에 지뢰가 없는 칸을 우선적으로 클릭한 후, 방문처리가 되지 않고 주변에 지뢰가 하나라도 있는 나머지 칸 수를 클릭 수에 더해주면 된다.

 

1. 각 좌표에서 주변에 지뢰가 몇 개 있는지 체크
  ➜ 주변에 지뢰가 몇 개 있는지는 중요한 부분이 아니므로 지뢰가 있으면 1, 지뢰가 없으면 0 으로 저장
2. 주변에 지뢰가 없는 칸(0)을 중심으로 BFS를 실행하며 주변 칸들을 방문처리 해준다.
3. 방문하지 않았으며 주변에 지뢰가 있는 칸(1)은 무조건 한 번씩 클릭해줘야 하므로 칸마다 클릭 수++

 

# 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
    static int n, result;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 };
    static int[] dy = { 0, 1, 1, 1, 0, -1, -1, -1 };

    public static void checkBomb(int x, int y) {
        boolean flag = false;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == -2) {
                // 지뢰가 주변에 하나라도 있다면 1저장
                board[x][y] = 1;
                return;

            }
        }
        board[x][y] = 0;
    }

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[] { x, y });
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            for (int i = 0; i < 8; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;

                    if (board[nx][ny] == 0)
                        q.add(new int[] { nx, ny });
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());

            board = new int[n][n];
            visited = new boolean[n][n];

            /*
             * 지뢰는 -2 , 지뢰가 없는 칸 -1 지뢰가 하나라도 있는 칸 1. 지뢰가 하나라도 없는 칸 0.
             */

            for (int i = 0; i < n; i++) {
                String str = br.readLine();
                for (int j = 0; j < n; j++) {
                    if (str.charAt(j) == '*')
                        board[i][j] = -2;
                    else
                        board[i][j] = -1;
                }
            }



            // 좌표들의 주변 지뢰 먼저 찾아주기
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (board[i][j] == -1)
                        checkBomb(i, j);

            for (int i = 0; i < n; i++) 
                for (int j = 0; j < n; j++) 
                    if (board[i][j] == 0 && !visited[i][j]) {
                        bfs(i, j);
                        result++;
                    }


            for (int i = 0; i < n; i++) 
                for (int j = 0; j < n; j++)
                    if (board[i][j] == 1 && !visited[i][j]) 
                        result++;


            sb.append('#').append(t).append(' ').append(result).append('\n');
            result = 0;
        }
        System.out.println(sb);
    }
}

코드에 대한 피드백은 언제나 환영입니다🧚🏻‍♀️