[SWEA] 1868번. 파핑파핑 지뢰찾기 - JAVA

🧷 문제 링크

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

SW Expert Academy

 

📄 풀이 과정

문제 유형 : 구현, BFS

 

문제를 정말 꼼꼼히 읽어야 안헷갈릴 수 있는 문제였다. 처음에 어떻게 구현할지 흐릿흐릿하긴 했지만, 0이 아닌 칸들도 클릭하면 8방이 클릭된 것으로 처리되는 것으로 생각해서 더 머리속이 복잡했다. 항상 천천히 꼼꼼히 문제를 읽고 계획을 세운 뒤 코드를 짜자고 다짐을 하지만 항상 마음이 급해지기 일쑤인 것 같다..ㅜ

• 입력이 끝나면 배열을 돌면서 각 칸 8방에 지뢰가 몇 개 있는지 표시해준다. (0인 칸을 알아내기 위해서)
• BFS 를 통해 0 인칸을 만나면 방문 처리(클릭)을 해주고 Que에 넣고 (내 코드에선 따로 방문 처리 배열 없이 지뢰와 같이 -1로 표시했다.) Que에서 빼내 8방을 방문 처리한다. 8방 안에 또 다른 0인 칸이 있다면 다시 Que에 넣어준다. 
• 모든 과정이 끝나면 방문하지 않은 칸들은 하나씩 클릭을 해줘야 하기 때문에 0보다 큰 칸들을 모두 더해 출력한다. 

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Solution_d4_1868_파핑파핑지뢰찾기 {
    
    static int[] di = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dj = {0, 1, 1, 1, 0, -1, -1, -1};
    
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input_d4_1868.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=1; tc<=T; tc++) {
            int N = Integer.parseInt(br.readLine());
            
            int[][] mat = new int[N][N];
            
            for(int i=0; i<N; i++) {
                String s = br.readLine();
                for(int j=0; j<N; j++) {
                    if(s.charAt(j)=='*') mat[i][j] = -1;        // 지뢰가 있는 곳을 -1로 표시
                    else mat[i][j] = 0;
                }
            }
            
            // 각 칸의 8방의 지뢰의 갯수를 찾는다.
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(mat[i][j] == 0) {
                        
                        int cnt =0;
                        for(int d=0; d<8; d++) {
                            int ni = i+di[d];
                            int nj = j+dj[d];
                            
                            if(ni<0 || ni>=N || nj<0 || nj>=N) continue;
                            if(mat[ni][nj]==-1) cnt++;
                        }
                        
                        mat[i][j] = cnt;
                    }
                }
            }
            
            // 0인 칸의 8방을 연쇄적으로 방문처리한다.
            Queue<int[]> que = new LinkedList<int[]>();
            int ans=0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(mat[i][j]==0) {
                        ans++;                            // 클릭 추가
                        que.offer(new int[] {i, j});
                        mat[i][j] = -1;                 // 방문 처리
                        
                        while(!que.isEmpty()) {
                            int[] cur = que.poll();
                            
                            for(int d=0; d<8; d++) {
                                int ni = cur[0] + di[d];
                                int nj = cur[1] + dj[d];
                                
                                if(ni<0 || ni>=N || nj<0 || nj>=N || mat[ni][nj]==-1) continue;
                                if(mat[ni][nj]==0) que.offer(new int[] {ni, nj});        // 8방에 또 0이 있다면 다시 que에 넣어 터트린다.
                                mat[ni][nj] = -1;        // 방문 처리
                            }
                        }
                    }
                }
            }
            
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(mat[i][j]>0) ans++;        // 클릭하지 않은 칸들
                }
            }
            
            sb.append("#").append(tc).append(" ").append(ans).append("\n");
        }
        
        System.out.print(sb.toString());
        br.close();
    }
 
}
 

 

📌 채점 결과