[백준] 2667번 - 단지 번호 붙이기 (DFS)

모든 단지를 방문해야 함! -> DFS를 사용한다.

 

   	static boolean isVisited[][];
    static int arr[][];
    static int count = 0, number = 0;
    static int nowX, nowY, N;
    static int dirX[] = {0, 0, -1, 1};
    static int dirY[] = {-1, 1, 0, 0};

 

dirX, dirY는 각각 좌우, 상하의 좌표 범위를 판단 할 수 있게 하기 위한 배열이다.

nowX, nowY는 현재의 범위를 계산한 좌표이다.

 

 

public static void DFS(int x, int y) {
        isVisited[x][y] = true;
        arr[x][y] = number;
        count++;

        for (int i = 0; i < 4; i++) {
            nowX = dirX[i] + x;
            nowY = dirY[i] + y;

            if (nowX >= 0 && nowY >= 0 && nowX < N && nowY < N) {
                if (arr[nowX][nowY] == 1 && !isVisited[nowX][nowY]) {
                    DFS(nowX, nowY);
                }
            }
        }

 

 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N][N];
        isVisited = new boolean[N][N];
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1 && !isVisited[i][j]) {
                    count = 0;
                    DFS(i, j);
                    list.add(count);
                }
            }
        }

        System.out.println(list.size());
        Collections.sort(list);


        for (int num : list) {
            System.out.println(num);
        }

    }

 

전체 배열을 탐색하면서 방문하지 않았고, arr 에서 1인 곳을 만날 경우 DFS() 메서드가 실행되도록 한다 

DFS()에서 방문 할 경우 isVisited[x][y] = true

단지 번호를 부여하기 위해 number 값을 arr[x][y]에 넣어준다.