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

출처: SWEA

 Input 

2

3

..*

..*

**.

5

..*..

..*..

.*..*

.*...

.*...

 

 

 Output 

#1 2

#2 8

문제에서는 최소 Click 횟수를 구하는 문제입니다.

최대한 연쇄폭파를 많이시켜서 Click 횟수를 최소화 시켜야 합니다.

　

주어진 Sample Case를 분석하면

『　』표시된 지역에서 '0'으로 표시된 곳 중 하나만 click하면 우측이미지랑 동일한 결과를 얻을 수 있다.

하지만 '1', '2'로 일어난 곳을 처음 Click했다면 연쇄폭발은 일어나지 않기에

최소 클릭 횟수를 만족 못합니다.

 

<처리 순서>

① 최소 클릭을 위해서 주위에 지뢰가 없는 지점을 연쇄 폭발 시킵니다.

② 과정 ①이 모두 끝나면 남은 지점(지뢰는 없지만 주변에는 지뢰가 있는)을 Count 합니다. 

    (②에서 count 되는 지점은 연쇄 폭발이 일어나지 않는 지점)

 

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Solution {
 
    // 8개의 위치 상하좌우, 대각선
    static public int[] dx = { 0, 0, -1, 1, -1, -1, 1, 1 };
    static public int[] dy = { -1, 1, 0, 0, -1, 1, -1, 1 };
    static public int answer, n;
    static public char[][] arr;
 
 
    public static void main(String[] args) throws Exception {
 
 
        Scanner sc = new Scanner(System.in);
         
        // TestCase
        int tc = Integer.parseInt(sc.next());
        int probNo = 1;
 
 
        while (tc-- > 0) {
            n = Integer.parseInt(sc.next());
            answer = 0;
            arr = new char[n][n];
             
            // Input Data 가공
            for(int i=0; i<n; i++) {
                String str = sc.next();
                for(int j=0; j<str.length(); j++) {
                    arr[i][j] = str.charAt(j);
                }
            }
             
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    // 지뢰가 없는 spot에서 주위 폭탄 여부 파악
                    if(arr[i][j] == '.' && checkNoBomb(new Vertex(i, j))) {
                        // 해당 지역 연쇄 폭파 시키기
                        BFS(new Vertex(i, j));
                         
                        // click 횟수 증가
                        answer++;
                    }
                }
            }
             
            // 방문 하지 않으면서 동시에 아직 연쇄 폭파되지 않은 곳을 count
            // 일일이 click 해줘야 된다.
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(arr[i][j] == '.') answer++;
                }
            }
             
            // 정답 출력
            System.out.print("#" + (probNo++) + " ");
            System.out.println(answer);
        }
    }
 
 
    private static void BFS(Vertex vertex) {
        Queue<Vertex> queue = new LinkedList<>();
        queue.add(vertex);
         
        while(queue.size() > 0) {
            Vertex start = queue.poll();
            // 주변에 폭탄이 없으면서 방문했다는 표시
            arr[start.x][start.y] = 'N';
             
            // 주변 영역 중 연쇄 폭파해야 될 곳 BFS
            for(int i=0; i<8; i++) {
                int nX = start.x + dx[i];
                int nY = start.y + dy[i];
                 
                // 범위를 벗어나면 skip
                if(nX < 0 || nY < 0 || nX >= n || nY >= n) continue;
                 
                // 이미 방문한 곳이라면 skip
                if(arr[nX][nY] == 'N' || arr[nX][nY] == 'Y') continue;
                 
                // 주변에 폭탄이 있는지 확인
                if(!checkNoBomb(new Vertex(nX, nY))) {
                    // 방문 표시 (연쇄폭발의 경계선)
                    arr[nX][nY] = 'Y';
                }else {
                    // 방문 표시
                    arr[nX][nY] = 'N';
                    // 해당 지점은 BFS 탐색 계속.
                    queue.add(new Vertex(nX, nY));
                }
            }
        }
    }
 
    private static boolean checkNoBomb(Vertex vertex) {
        // 주변이 지뢰인지 확인
        for (int i = 0; i < 8; i++) {
            int nX = vertex.x + dx[i];
            int nY = vertex.y + dy[i];
 
 
            // 범위를 벗어나면 continue
            if (nX < 0 || nY < 0 || nX >= n || nY >= n)
                continue;
 
 
            // 주위에 한개라도 폭탄이 있다면
            if (arr[nX][nY] == '*') return false;
        }
        // 주위에 폭탄이 없을 경우
        return true;
    }
}
 
 
class Vertex {
    int x, y;
    public Vertex(int x, int y) {
        this.x = x;
        this.y = y;
    }
}