[자바] SWEA 1868 : 파핑파핑 지뢰찾기 (D4)

[자바] SWEA 1868 : 파핑파핑 지뢰찾기 (D4)

• SWEA 1868 : 파핑파핑 지뢰찾기

---

풀이

방향성 생각

• 약간 그리디하게 접근해야한다.
• 0을 누르면 주변에 있는 1 이상의 숫자에 대해서도 탐지를 해주니, 0에서 먼저 BFS를 돌리고 이후에 1 이상 숫자들을 처리하기.

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    static int N;
    static int[][] arr;
    static boolean[][] V;
    static int[][] dires = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    static Map<Character, Integer> cvt = new HashMap<Character, Integer>() {{
        put('*', -1);
        put('.', 0);
    }};


    static boolean inside(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }

    static void bfs(int sx, int sy) {
        V[sy][sx] = true;
        ArrayDeque<int[]> Q = new ArrayDeque<>();
        Q.offer(new int[]{sx, sy});

        while (!Q.isEmpty()) {
            int[] cur = Q.poll();
            int x = cur[0], y = cur[1];

            for (int[] dir : dires) {
                int nx = x + dir[0], ny = y + dir[1];
                if (inside(nx, ny) && !V[ny][nx]) {
                    V[ny][nx] = true;
                    if (arr[ny][nx] == 0) {
                        Q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= TC; tc++) {
            N = Integer.parseInt(br.readLine().trim());

            arr = new int[N][N];
            for (int i = 0; i < N; i++) {
                String line = br.readLine().trim();
                for (int j = 0; j < N; j++) {
                    arr[i][j] = cvt.get(line.charAt(j));
                }
            }

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    if (arr[y][x] == -1) {
                        for (int[] dir : dires) {
                            int nx = x + dir[0], ny = y + dir[1];
                            if (inside(nx, ny) && arr[ny][nx] >= 0) {
                                arr[ny][nx]++;
                            }
                        }
                    }
                }
            }

            V = new boolean[N][N];
            int count = 0;

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    if (arr[y][x] == 0 && !V[y][x]) {
                        bfs(x, y);
                        count++;
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (arr[i][j] > 0 && !V[i][j]) {
                        count++;
                    }
                }
            }

            sb.append("#").append(tc).append(" ").append(count).append("\n");
        }

        System.out.print(sb.toString());
    }
}

코멘트

• .