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

BFS를 사용하는 문제이다.

해당 칸의 값이 0이면 8칸의 값을 무조건 방문해줘야하기에 전체 배열을 돌면서 0인 곳을 찾아서 방문해주는 BFS 로직을 우선 사용하였다. 그리고 모든 방문이 끝난후 아직 방문하지 않고, 빈칸인 경우들의 대해서 count를 추가해주는 과정을 거쳐 답을 구하였다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Solution_d4_1868_파핑파핑지뢰찾기 {
    
    static int[] di = {-1,-1,-1,0,1,1,1,0};
    static int[] dj= {-1,0,1,1,1,0,-1,-1};
    
    static char[][] map;
    static boolean[][] visit;
    static int N;
    static int count=0;
    
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j;
        public Pos(int i,int j) {
            this.i=i;this.j=j;
        }
    }
    
    public static void main(String[] args) throws Exception {
        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());
            map=new char[N][N];
            visit= new boolean[N][N];
            queue=new LinkedList<>();
            
            for(int i=0;i<N;i++) {
                String str=br.readLine();
                for(int j=0;j<N;j++) {
                    map[i][j]=str.charAt(j);
                }
            }
            
            count=0;
            bfs();
            System.out.println("#"+tc+" "+count);
        }
        
        
    }
    
    static boolean isZero(int i,int j) {
        boolean zero=true;
    
        for(int dir=0;dir<8;dir++) {
            int nextI= i+di[dir];
            int nextJ= j+dj[dir];
            
            if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=N)
                continue;
            
            if(map[nextI][nextJ]=='*') {
                zero=false;
                break;
            }
        }
        return zero;
    }
    
    static void bfs() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(map[i][j]=='.' && visit[i][j]==false && isZero(i, j)==true) {
                    queue.offer(new Pos(i, j));
                    visit[i][j]=true;
                    count++;
//                    System.out.println(i+","+j);
                    
                    while(!queue.isEmpty()) {
                        Pos cur =queue.poll();
                        
                        for(int dir=0;dir<8;dir++) {
                            int nextI= cur.i+di[dir];
                            int nextJ= cur.j+dj[dir];
                            
                            if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=N)
                                continue;
                            
                            if(map[nextI][nextJ]=='.' && visit[nextI][nextJ]==false) {
                                if(isZero(nextI, nextJ)) {
                                    queue.add(new Pos(nextI, nextJ));
                                    visit[nextI][nextJ]=true;
                                }else
                                    visit[nextI][nextJ]=true;
                            }
                            
                        }
                        
                    }
                }
                
            }
        }
        
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(map[i][j]=='.' && visit[i][j]==false) {
                    count++;
                }
            }
        }
        
        
    }
}