[SWEA]1868. 파핑파핑 지뢰찾기(dfs, bfs).java

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

처음에 문제 접근을 완전히 잘못해서 갈아엎었다..

문제를 확실히 이해하고 구현하자 좀~~~!

여러 해결 방법이 있겠지만

1. 각 좌표에서 주변에 지뢰가 몇 개 있는지 체크

2. 주변에 지뢰가 없는 곳만 먼저 눌러주기

3. 2번 과정을 수행한 후에도 아직 눌리지 않은 좌표 눌러주기

#. Code_bfs

visit 처리는 boolean 배열을 사용하지 않고,

주변 지뢰 개수를 저장하는 count 배열에 -1 로 표시해주었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110

import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue;   public class Solution1868_bfs {       static int N, res, mCnt[][];     static char map[][];     static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 }, dy = { 0, 1, 1, 1, 0, -1, -1, -1 };       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           int T = Integer.parseInt(br.readLine());         for (int tc = 1; tc <= T; tc++) {               N = Integer.parseInt(br.readLine());             res = 0;             map = new char[N][N];             mCnt = new int[N][N];             // 지뢰밭 입력             for (int i = 0; i < N; i++) {                 map[i] = br.readLine().toCharArray();             }               // 주변 지뢰 개수 세기             countMine();               // 주변에 지뢰가 없는 곳부터 눌러주자.             for (int i = 0; i < N; i++) {                 for (int j = 0; j < N; j++) {                     // 주변에 지뢰가 없고 현 위치가 지뢰가 아니라면                     if(mCnt[i][j] == 0 && map[i][j] != '*') {                         click(i, j);                         res++;                     }                 }             }                          // 아직 눌리지 않은 곳이 있다면 눌러주자.             for (int i = 0; i < N; i++) {                 for (int j = 0; j < N; j++) {                     // 주변에 지뢰가 있지만 현 위지가 지뢰가 아니라면                     if(mCnt[i][j] > 0 && map[i][j] != '*') {                         res++;                     }                 }             }                          System.out.println("#" + tc + " " + res);         }       }       private static void click(int x, int y) {           Queue<Point> q = new LinkedList<>();         q.add(new Point(x, y));         // 방문 체크         mCnt[x][y] = -1;                  while(!q.isEmpty()) {                          Point now = q.poll();             // 주변 탐색             for (int d = 0; d < 8; d++) {                 int xx = now.x + dx[d];                 int yy = now.y + dy[d];                 // 범위를 벗어거나 이미 눌린 곳이거나 지뢰라면 pass                 if(xx < 0 || xx >= N || yy < 0 || yy >= N                          || mCnt[xx][yy] == -1 || map[xx][yy] == '*') continue;                 // 주변 좌표도 지뢰 count가 0이라면 queue에 추가해주자.                 if(mCnt[xx][yy] == 0) {                     q.add(new Point(xx, yy));                 }                 // 방문 체크                 mCnt[xx][yy] = -1;             }         }              }          private static void countMine() {                  for (int x = 0; x < N; x++) {             for (int y = 0; y < N; y++) {                 // 클릭할 수 있는 곳이라면 주변에 지뢰가 몇개 있는지 세보자.                 if(map[x][y] == '.') {                     int cnt = 0;                     for (int d = 0; d < 8; d++) {                         int xx = x + dx[d];                         int yy = y + dy[d];                         // 범위를 벗어거나 지뢰가 아니면 pass                         if(xx < 0 || xx >= N || yy < 0 || yy >= N || map[xx][yy] != '*') continue;                                                  cnt++;                     }                                          mCnt[x][y] = cnt;                 }             }         }              }   } Colored by Color Scripter

cs

#. Code_dfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Solution1868_dfs {
 
    static int N, res, mCnt[][];
    static char map[][];
    static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 }, dy = { 0, 1, 1, 1, 0, -1, -1, -1 };
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            N = Integer.parseInt(br.readLine());
            res = 0;
            map = new char[N][N];
            mCnt = new int[N][N];
            // 지뢰밭 입력
            for (int i = 0; i < N; i++) {
                map[i] = br.readLine().toCharArray();
            }
 
            // 주변 지뢰 개수 세기
            countMine();
 
            // 주변에 지뢰가 없는 곳부터 눌러주자
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 주변에 지뢰가 없고 현 위치가 지뢰가 아니라면
                    if(mCnt[i][j] == 0 && map[i][j] != '*') {
                        click(i, j);
                        res++;
                    }
                }
            }
            
            // 아직 눌리지 않은 곳이 있다면 눌러주자.
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 주변에 지뢰가 있지만 현 위지가 지뢰가 아니라면
                    if(mCnt[i][j] > 0 && map[i][j] != '*') {
                        res++;
                    }
                }
            }
            
            System.out.println("#" + tc + " " + res);
        }
 
    }
 
    private static void click(int x, int y) {
 
        int now = mCnt[x][y]; 
        // 방문 처리
        mCnt[x][y] = -1;
 
        // 주변에 지뢰가 없는 좌표라면
        if(now == 0) {
            // 주변 탐색
            for (int d = 0; d < 8; d++) {
                int xx = x + dx[d];
                int yy = y + dy[d];
                // 범위를 벗어거나 눌린 곳이거나 지뢰라면 pass
                if(xx < 0 || xx >= N || yy < 0 || yy >= N 
                        || mCnt[xx][yy] == -1 || map[xx][yy] == '*') continue;
 
                click(xx, yy);
            }
        }
        
    }
    
    private static void countMine() {
        
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                // 클릭할 수 있는 곳이라면 주변에 지뢰가 몇개 있는지 세보자.
                if(map[x][y] == '.') {
                    int cnt = 0;
                    for (int d = 0; d < 8; d++) {
                        int xx = x + dx[d];
                        int yy = y + dy[d];
                        // 범위를 벗어거나 지뢰가 아니면 pass
                        if(xx < 0 || xx >= N || yy < 0 || yy >= N || map[xx][yy] != '*') continue;
                        cnt++;
                    }
                    
                    mCnt[x][y] = cnt;
                }
            }
        }
        
    }
 
}