SWEA[1868] - 파핑파핑 지뢰찾기[D4]

링크

SWEA[1868]

문제설명

• 그래프의 연결성 탐색 문제

문제풀이

• 0인칸중 연결된 0칸 탐색 후, 0인칸 주변칸 드러낸 뒤에 나머지 칸 count.

문제코드

import java.util.LinkedList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Solution{

    public static int[][]     dir= {
            {-1,0},
            {-1,1},
            {0,1},
            {1,1},
            {1,0},
            {1,-1},
            {0,-1},
            {-1,-1}
    };

    public static int Ans=0;
    public static int N;
    public static char[][] map;
    public static boolean[][] visit;

    public static boolean is_0(int[]rc) {
        int nr;
        int nc;

        for (int d = 0; d < 8; d++) {
            nr = rc[0] + dir[d][0];
            nc = rc[1] + dir[d][1];
//            경계 안에서
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
//                지뢰가 하나라도 있으면
                if(map[nr][nc]=='*') {
                    return false;
                }
            }
        }
//        지뢰 없음
        return true;
    }

    public static boolean non_0(int[]rc) {
        int nr;
        int nc;

        for (int d = 0; d < 8; d++) {
            nr = rc[0] + dir[d][0];
            nc = rc[1] + dir[d][1];
//            경계 안에서
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
//                0인칸(true)가 하라나도 있으면
                if(visit[nr][nc]) {
                    return false;
                }
            }
        }
//        0인칸(true)
        return true;
    }

    public static void main(String args[]) throws Exception
    {
        //System.setIn(new FileInputStream("res/swea/1868.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        T=Integer.parseInt(br.readLine().trim());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = Integer.parseInt(br.readLine());
            map = new char[N][N];
            visit = new boolean[N][N];

            for (int i = 0; i < N; i++) {
                map[i] = br.readLine().toCharArray();
            }

            LinkedList<int[]> q = new LinkedList<int[]>();
            int[] now;
            int nr;
            int nc;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
//                    방문 가능한 경우 ('.' && visit false) && 0인 경우
                    if(map[i][j]=='.' && !visit[i][j] && is_0(new int[] {i,j})) {
                        Ans++;
                        visit[i][j]=true;
                        q.add(new int[] {i,j});
                        while(!q.isEmpty()) {
                            now = q.poll();
                            for (int d = 0; d < 8; d++) {
                                nr = now[0] + dir[d][0];
                                nc = now[1] + dir[d][1];
//                                경계안에서 그 다음칸도 0이면
                                if(nr>=0 && nr<N && nc>=0 && nc<N && !visit[nr][nc] && is_0(new int[] {nr,nc})) {
                                    visit[nr][nc]=true;
                                    q.add(new int[] {nr,nc});
                                }
                            }
                        }
                    }
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(visit[i][j]==false && map[i][j]=='.' && non_0(new int[] {i,j})) {
                        Ans++;
                    }
                }
            }

            System.out.println("#"+test_case+" "+Ans);
//            초기화
            Ans=0;
        }
    }
}

아쉬운점

• 지뢰 갯수 표시하는 기능은 안만들었음, 굳이 필요없는거같아서
• 어찌저찌 답구하는거 주먹구구식으로 한듯

잘한점

• 8방탐색
• 그래프 연결성 검사를 BFS로 함
• 30min