[자바] 백준 2667번 단지번호 붙이기 (BFS/DFS) 2021-06-15

 우선 문제를 보자마자 그래프 탐색 알고리즘을 이용하여 "연결요소"의 개수를 파악한 다음 그걸 리스트에 담고, 리스트를 정렬해준 다음, 차례로, 리스트 사이즈출력, 리스트요소들 하나씩 출력 해주면 끝난다. 풀이법을 생각해내는데 5분도 걸리지 않았지만.... 실제 정답을 내는데 디버깅 포함 1시간 걸린거 같다...

 

내가 실수한 부분은, 이 문제는 "최단거리"나, "백트레킹" 등, 그래프 탐색에 있어서 특수한 조건이 없기 때문에, DFS또는 BFS중 아무거나 사용 가능하다. 이유는 두 기법 모두, 연결된 노드를 전부 방문할수 있고, 그에 맞춰서 카운트 값을 올려줄수 있기 때문이다. 어제 쓴 포스트에서는 BFS를 이용해서 풀었기에, DFS로 풀어볼까 하면서 코드를 짰더니... 계속 리스트 사이즈 1, 값은 48이라는 값이 나온다.. 그래서 가만히 생각해 보니, 리스트 사이즈가 1이란 것은, 연결요소의 개수가 1개 뿐이라는 것이고, 그 연결요소의 크기는 48이라는 말도안되는 값이 나왔다. 

그런데 난 이 오류값으로부터, 나의 실수를 찾았다.

첫번째출력값(리스트사이즈) 1: 내가 어떤 조건을 빠트렸기에, 재귀함수가 모든 노드를 다 방문했을 것이다. 

48: 예제를 입력했으므로 7*7=49인데 첫번째꺼 제외해서 48이다.

 

그래서 원래라면, DFS로 해도 무관하지만, 난 내가 틀린줄 알고, BFS로 다시 했다...ㅋㅋㅋ

 

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] value;
    static int[] dx={-1,+1,0,0};
    static int[] dy={0,0,-1,+1};
    static List<Integer> list=new LinkedList<>();
    static int cnt=0;
    static int N;


    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
         N = s.nextInt();
        char[][] charr = new char[N][];
        value = new boolean[N][N];
        s.nextLine();

        for (int i = 0; i < N; i++) {
            charr[i] = s.nextLine().toCharArray();//공백없이 주어진 값들을 String에서
            //Integer로 바로 변환 불가함. 이유? 첫 글자가 0일시, 0 액면가로 안나오고 사라짐.
        }

        int[][] arr = new int[N][N];
        for (int i = 0; i < charr.length; i++) {
            for (int j = 0; j < charr[i].length; j++) {
                int now = Integer.valueOf(charr[i][j]-48);
                arr[i][j] =  now;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                int now=arr[i][j];
                if(now==1){
                    bfs(arr,i,j);
                    list.add(cnt);
                    cnt=0;

                }
            }

        }
        Collections.sort(list);
        System.out.println(list.size());
        for (Integer integer : list) {
            System.out.println(integer);
        }
        }
       public  static  void bfs(int[][] arr,int i,int j){
        value[i][j]=true;
        Queue<Point> queue=new LinkedList<>();
        cnt++;
       queue.add(new Point(i,j));
        while(!queue.isEmpty()) {
            Point now= queue.poll();
            int nowi= now.x;
            int nowj=now .y;

            for (int x = 0; x < dx.length; x++) {
                int nexti = nowi + dx[x];
                int nextj = nowj + dy[x];
                if (nexti < 0 || nextj < 0 || nexti >= N || nextj >= N) {
                    continue;
                }
                if (value[nexti][nextj]||arr[nexti][nextj]==0) {
                    continue;
                }
                value[nexti][nextj] = true;
                arr[nexti][nextj] = 0;
                cnt++;
                queue.add(new Point(nexti,nextj));
            }
        }

       }

    }
    class Point{
    int x;
    int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

 

공부시간 1시간

순공부시간 40분.

 

오늘 오전에 외근 병원 갔다온다고 많이 공부 못한거 같다.