파핑파핑 지뢰찾기

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

SW Expert Academy

 

알고리즘

1. 이중 포문을 돌면서 8방향 지뢰의 개수를 찾는다.

2. 지뢰개수가 0인 좌표를 큐에 넣고 조건을 만족 하는 범위까지 퍼진다.

3. 안 퍼진 곳(0)과 퍼진곳의 시작 좌표(-1)을 count해준다.

 

주의사항

1. 구현 하는 방식은 다양하다. 알고리즘을 생각할 때 문제를 잘 읽어보고 문제대로 구현한다.

 

구현

class Solution
{
    static int N;
    static char map[][];
    static int temp[][];
    static int check[][];
    static int dir[][] = {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            N = Integer.parseInt(in.readLine().trim());
            check = new int[N][N];
            temp = new int[N][N];
            map = new char[N][N];
            LinkedList<int []> queue = new LinkedList<int[]>();
            LinkedList<int []> queue1 = new LinkedList<int[]>();
            for (int i = 0; i < N; i++) {
                String s = in.readLine();
                for (int j = 0; j < N; j++) {
                    map[i][j] = s.charAt(j);
                    if(map[i][j] == '*')
                        check[i][j] = -1;
                }
            }
            ///지뢰 개수 표시//////////////

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                        int cnt = 0;
                        for (int j2 = 0; j2 < 8; j2++) {
                            int ny = i+dir[j2][0];
                            int nx = j+dir[j2][1];
                            if(ny < N &&nx < N &&ny > -1 &&nx>-1 && map[ny][nx] == '*')
                                cnt++;
                            }
                        temp[i][j] = cnt;
                    }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(temp[i][j] == 0 && check[i][j] == 0) // 주위에 지뢰가 없고, 체크가 안되있으면
                    {
                        queue.offer(new int[] {i,j});
                        check[i][j] = 1;
                        while(!queue.isEmpty())
                        {
                            int te[] = queue.poll();
                            int y = te[0];
                            int x = te[1];
                            int cnt = check[y][x];
                            for (int k = 0; k < 8; k++) {
                                int ny = y+dir[k][0];
                                int nx = x+dir[k][1];
                                if(ny < N && nx<N && ny>-1 && nx>-1 && check[ny][nx] ==0) //체크가 안되있으면
                                {
                                    check[ny][nx]=cnt+1; //1부터 하나씩 증가하게함 -> 나중에 0과 1만 카운트하면 최소 클릭 개수임
                                    if(temp[ny][nx] == 0) //주위에 지뢰0개인 칸이 있으면 offer함
                                    {
                                        queue.offer(new int[] {ny,nx});
                                    }
                                }
                            }
                        }
                    }
                }
            }

            int cnt=0;
            for (int i1 = 0; i1 < N; i1++) {
                for (int j = 0; j < N; j++) {
                    if(check[i1][j] == 1 || check[i1][j] == 0) //0또는 1만 카운트함
                        cnt++;
                }
            }
            System.out.println("#"+test_case+" "+cnt);
        }
    }
}