SWEA 1868 파핑파핑 지뢰찾기

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class PapingPaping {
    static int N;
    static char[][] map;
    static int[] dr = {0,1,1,1,0,-1,-1,-1};
    static int[] dc = {1,1,0,-1,-1,-1,0,1};
    static int click;
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            map = new char[N][N];
            click = 0;
            for (int i = 0; i < N; i++) {
                String str = sc.next();
                for (int j = 0; j < N; j++) {
                    map[i][j] = str.charAt(j);
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]=='.'){
                        boolean flag = false;
                        for (int k = 0; k < 8; k++) {
                            int row = i+dr[k];
                            int col = j+dc[k];
                            if(row<0||col<0||row>=N||col>=N) continue;
                            if(map[row][col]=='*') flag = true;
                        }
                        if(!flag){
                            bfs(i,j);
                            click++;
                        }
                    }
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]=='.'){
                        click++;
                    }
                }
            }
            System.out.println("#"+test_case+" "+click);
        }
    }
    public static void bfs(int row, int col){
        Queue<int[]> que = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        que.add(new int[]{row,col});
        visited[row][col]= true;
        map[row][col] = '0';
        while (!que.isEmpty()){
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];

            for (int i = 0; i < 8; i++) {
                int nrow = crow + dr[i];
                int ncol = ccol + dc[i];
                int count = 0;
                if(nrow<0||ncol<0||nrow>=N||ncol>=N) continue;
                for (int j = 0; j < 8; j++) {
                    int nnrow = nrow + dr[j];
                    int nncol = ncol + dc[j];
                    if(nnrow<0||nncol<0||nnrow>=N||nncol>=N) continue;
                    if(map[nnrow][nncol]=='*') count++;
                }

                map[nrow][ncol]=(char)(count + '0');

                if(!visited[nrow][ncol]&&map[nrow][ncol]=='0'){
                    visited[nrow][ncol] = true;
                    que.add(new int[]{nrow,ncol});
                }
            }
        }
    }
}

문제조건

1. 지뢰가 없는 부분 누를시, 누른부분의 8방향 모두 지뢰가 없다면, 주변 8방향 모두 연쇄적으로 숫자가 나타난다.
2. 연쇄적으로 숫자가 나타날때, 0이 나타나면, 계속 연쇄가 일어나고, 0이 아니라면, 연쇄가 일어나지 않는다.

풀이방법

📢 map을 탐색시, 8방향 모두 지뢰가 없는 좌표를 찾아 bfs로 넘겨준다.
연쇄작용으로 map에 숫자를 표시하고, 나머지 지뢰아닌 부분을 click에 더해준다.

1. map을 탐색시, 8방향 모두 지뢰가 없는 좌표를 찾아 bfs로 넘겨주고, click을 늘려준다(한번 터치)
2. 주변 8칸에 숫자를 써 넣는데, 각 8칸마다 다시 주변 8칸에 지뢰갯수를 확인한다.
3. 주변 8칸에 지뢰의 갯수만큼 숫자를 써넣는다.
4. 지뢰의 갯수가 0인 칸만 다시 que에 넣어 연쇄작용을 시켜준다.

-> 나는 8방향 모두 지뢰가 없는 좌표를 찾아서 bfs로 넘겼지만,
아무 숫자나 넘겨도 어차피 0인 칸만 다시 que에 넣어서 연쇄작용하면 되므로, 해당 로직은 굳이 필요는 없다.

후기

큐안에 이중포문이 되어있는 구조는 처음풀어서 신박했다.
bfs응용을 할때는 항상 que에 어떤 조건일때만 넣어야 하는지가 중요한것 같다.

별개로 알게 된점
int형 배열 map에 char형 문자를 넣을때는 형변환이 필요없이 자동으로 형변환이 된다.

int[][] map = new int[N][N];
char c = 9;
map[0][0] = c-'0';

하지만 char형 배열map에 int형 숫자를 넣을때는 형변환이 필요하다.

char[][] map = new char[N][N];
int num = 9;
map[0][0] = (char)(num+'0');

👉이유는 char은 8비트를 사용하며 보통 -128부터 127까지의 값을 나타낸다. 그러나 int는 4바이트를 사용하며 훨씬 더 넓은 범위의 값을 나타낼 수 있다.
따라서 int형을 char형에 넣으려 하면 데이터 손실이 발생하기 때문에 자동으로 형변환이 되지 않는 것이다.

int형에 문자넣기
map[0][0] = c-'0';

char형에 숫자넣기
map[0][0] = (char)(num+'0');
👉해당 구조도 자주 사용되므로 알아두자