SWEA 1868. 파핑파핑 지뢰찾기 :: 돼지개발자

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

"가장 많이 열리는 걸 열고, 그다음에 차근차근."

알고리즘 기본 로직은 맵에서 주위에 지뢰가 없는 칸을 탐색해 먼저 클릭하여 해당 칸을 오픈한다. 이렇게 오픈된 나머지 8칸에 대해서도 똑같은 검사를 한다. 이렇게 하여 주위에 지뢰가 없는 칸들이 모두 없어 지게 되고, 그 후에 남아있는 칸들의 수를 세서 최종 값을 더한다.

이때, 지뢰가 없는 칸의 탐색은 BFS를 통해 한다. 더해서 아래 큐에 들어가는 중에 중복이 생겨났었고, 시간초과가 났다. 탐색은 중복을 줄이는 것이 정말 중요하다. visited 배열을 두어 다시 들어가지 않도록 했음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Solution {
 
    static int T;
    static int N;
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,-1,-1,0,0,1,1,1};
    static int[] dy = {-1,0,1,-1,1,-1,0,1};
    static Queue<Integer> q = new LinkedList<>();
    static int cnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        
        int t = 1;
        while(T-- >0) {
            N = Integer.parseInt(br.readLine());
            
            map = new char[N][N];
            visited = new boolean[N][N];
            
            for (int i = 0; i < N; i++) {
                map[i] = br.readLine().toCharArray();
            }
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    
                    if(map[i][j] != '.') continue;
                    
                    int mine = 0;
                    
                    for (int k = 0; k < 8; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        
                        if(isRange(nx, ny) && map[nx][ny] == '*') {
                            mine ++;
                        }
                    }
                    
                    if(mine == 0) {
                        q.add(i);
                        q.add(j);
                        solve();    
                    }
                }
            }
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j] == '.') cnt++;
                }
            }
            System.out.printf("#%d %d\n",t++,cnt);
            cnt = 0;
        }
    }
    
    static void solve() {
        cnt++;
        while(!q.isEmpty()) {
            int x = q.poll();
            int y = q.poll();
            
            int mine = 0;
            
            for (int k = 0; k < 8; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                
                if(isRange(nx, ny) && map[nx][ny] == '*') {
                    mine++;
                }
            }
            
            if(mine == 0) {
                map[x][y] = 'x';
                
                for (int k = 0; k < 8; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    if(!isRange(nx, ny) || map[nx][ny] != '.' || visited[nx][ny]) 
                        continue;
                    
                    visited[nx][ny] = true;
                    
                    q.add(nx);
                    q.add(ny);
                }
            }
            else {
                map[x][y] = 'x';
            }
        }
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}