[SWEA 1868] 파핑파핑 지뢰찾기 - JAVA

문제 링크

문제 정의

• 보드 내에 지뢰가 주어짐
• 지뢰 찾기의 룰과 동일
  • 보드 내에 지뢰가 존재
  • 현재 위치에서 8면에 지뢰가 없는 경우 8면에 지뢰가 존재하는 위치까지 확산
  • 현재 위치에서 8면에 지뢰가 존재한다면 개수를 출력하고 확산 중지

위와 같을 경우 지뢰 찾기 문제를 해결할 수 있는 최소 클릭 수를 구해라

접근 방법

8면에 지뢰가 없는 위치에서는 확산을 하고 8면에 지뢰가 존재하면 확산하지 않습니다.
DFS BFS에서 볼 수 있는 Flood Fill로 풀 수 있을 것 같습니다.

로직 순서는 아래와 같습니다.
1. 보드 초기화
2. 보드를 순회하며 지뢰를 찾을 경우 8면에 x 마킹
3. 다음 순회에서는 주변에 지뢰가 없는 필드에 대해서 dfs로 Flood Fill 수행하고 count 증가
4. 다음 순회에서는 전이가 안되는 주변에 지뢰가 존재하는 필드에 대해서 count 증가

dfs 탐색을 8면을 해야한다는 것을 제외하면 기본적인 로직이므로 설명은 생략하겠습니다.

코드

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

public class Solution {
    static StringTokenizer st;
    static int N;
    static int[] dy = {-1, 0, 1, 0, -1, -1, 1, 1};
    static int[] dx = {0, -1, 0, 1, -1, 1, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            char[][] board = new char[N][];

            for (int i = 0; i < N; i++) {
                board[i] = br.readLine().toCharArray();
            }

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    if (board[y][x] == '*') {
                        for (int d = 0; d < 8; d++) {
                            int ny = y + dy[d];
                            int nx = x + dx[d];

                            if (ny < 0 || ny >= N || nx < 0 || nx >= N || board[ny][nx] != '.') continue;
                            board[ny][nx] = 'x';
                        }
                    }
                }
            }

            int answer = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == '.') {
                        board[i][j] = '*';
                        dfs(i, j, board);
                        answer++;
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == 'x') {
                        board[i][j] = '*';
                        answer++;
                    }
                }
            }

            sb.append("#").append(t).append(" ").append(answer).append("\n");
        }

        System.out.print(sb);
    }

    static void dfs(int y, int x, char[][] board) {
        for (int d = 0; d < 8; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];

            if (ny < 0 || ny >= N || nx < 0 || nx >= N || board[ny][nx] == '*') continue;

            if (board[ny][nx] == '.') {
                board[ny][nx] = '*';
                dfs(ny, nx, board);
            }
            else {
                board[ny][nx] = '*';
            }
        }
    }
}