[SWEA]1868. 파핑파핑 지뢰찾기 D4 - Java

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

SW Expert Academy

 

지뢰찾기에서 지뢰가 아닌것만을 클릭한다고 가정할때 가장 적은 클릭횟수로 지뢰가 아닌 부분을 다 찾는문제이고 최소 클릭횟수를출력하는 문제이다. 지뢰는 '*' 지뢰가 아닌것은 '.' 로 입력받는다

 

풀이 

1.

반복문을 통해 순서대로 지뢰가 아닌 '.' 인 부분을

이웃한 8방향에 지뢰가 있는지 검사하는isClean(int y , int x, int n) 함수 선언 

클릭할때 동작하는 dfs(int y, int x, int n)함수 선언 

2.

클릭을 처리하는 dfs가 지뢰가 존재하지 않는 부분에 이웃한 8방향에 숫자를 나타낸다.

이때 해당 부분에도 지뢰가 하나도 존재하지 않을경우 dfs로 또 처리된다.

3.

최종적으로 

isClean 함수가 참이면, 즉 이웃한 8방향에 지뢰가 없으면 clickCnt변수 증가

나머지 지뢰가 아닌 부분은 그냥 클릭한다고 가정해서 clickCnt증가하면

최소 클릭횟수를 구할 수 있다.

 

 

전체코드

import java.util.*;
public class Main {
    static char[][] arr;
    static int clickCnt;
    static int[] dy = {-1,-1,0,1, 1,1,0,-1};
    static int[] dx = {0,1,1,1, 0,-1,-1,-1};
    static public void dfs(int y, int x, int n){
        int cnt=0; //발견한 지뢰
        for(int i=0;i<8;i++){
            int ny = y+ dy[i];
            int nx = x+ dx[i];
            boolean pass = ny>=0 && ny<n && nx>=0 && nx<n;
            if(pass && arr[ny][nx] == '*') cnt++;
        }
        arr[y][x] = (char)(cnt+'0');
        // 지뢰 발견안되면 8방향 또 탐색
        if(cnt==0){
            for(int i=0;i<8;i++){
                int ny = y+ dy[i];
                int nx = x+ dx[i];
                boolean pass = ny>=0 && ny<n && nx>=0 && nx<n && arr[ny][nx]=='.';
                if(pass){
                    dfs(ny,nx,n);
                }
            }
        }
    }
    static public boolean isClean(int y , int x, int n){
        int cnt=0; //발견한 지뢰
        for(int i=0;i<8;i++){
            int ny = y+ dy[i];
            int nx = x+ dx[i];
            boolean pass = ny>=0 && ny<n && nx>=0 && nx<n;
            if(pass && arr[ny][nx] == '*') cnt++;
        }
        if(cnt==0)return  true;
        else return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        clickCnt=0;
        int n = sc.nextInt();
        arr = new char[n][n];
        for(int i=0;i<n;i++){
            String s = sc.next();
            for(int j=0;j<n;j++){
                arr[i][j] = s.charAt(j);
            }
        }
        // 8방향 모두 지뢰가 없으면 클릭처리 후 dfs
        for(int i=0;i<n;i++) {
            for (int j = 0; j < n; j++) {
                if(arr[i][j]=='.' && isClean(i,j,n) ) {
                    clickCnt++;
                    dfs(i,j,n);
                }
            }
        }
        // 남은 지뢰가 아닌 부분만 더함
        for(int i=0;i<n;i++) {
            for (int j = 0; j < n; j++) {
                if(arr[i][j]=='.')clickCnt++;
            }
        }
        System.out.println(clickCnt);
    }
}