[백준 2667 : JAVA] 단지번호붙이기 / DFS

개요

 

dfs를 이용하여 <그림 1>을 <그림 2>의 형태의 배열로 만든다.

단절되어 있는 단지들의 집의 개수를 구하면 된다.

dfs를 통해 한 노드에서 갈 수 있는 노드 모두를 탐색하면서 풀이한다.

 

문제

 

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

 

풀이

 

DFS를 이용한다. dfs(int x, int y)메소드는 다음과 같이 동작한다. 

 

1. 현재 노드를 방문처리한다.
2. 현재 노드에서 상, 하, 좌, 우의 노드로 갈 수 있는지 확인한다.(이때 범위가 초과했는지, 집이 존재하는지 확인한다.)
   1. 갈 수 있다면 dfs()메소드를 호출한다
3. 2를 반복하며 집의 개수를 반환한다. 단, 집의 개수를 증가시키며 반환한다.

전부 끝나면 집의 개수를 오름차순 정렬하여 출력한다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static int[][] arr;
    static boolean[][] check;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];
        check = new boolean[n + 1][n + 1];
        // 단지 별 집의 개수를 저장하는 list
        List<Integer> list = new ArrayList<>();

        // input값을 배열에 저장
        for(int i = 1; i <= n; i++){
            String input = br.readLine();
            for(int j = 1; j <= n; j++){
                arr[i][j] = input.charAt(j - 1) - '0';
            }
        }

        // 깊이우선 탐색 진행
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(checkLocation(i, j)) {
                    // 단지번호를 뜻함
                    int val = dfs(i, j);
                    list.add(val);
                }
            }
        }

        Collections.sort(list);
        sb.append(list.size() + "\n");
        for(int num : list) sb.append(num + "\n");

        System.out.println(sb);
    }
    public static int dfs(int x, int y){
        // 단지 별 집의 개수
        int val = 1;
        check[x][y] = true;

        // '상'의 좌표
        if(checkLocation(x - 1, y)) val += dfs(x - 1, y);
        // '우'의 좌표
        if(checkLocation(x, y + 1)) val += dfs(x, y + 1);
        // '하'의 좌표
        if(checkLocation(x + 1, y)) val += dfs(x + 1, y);
        // '좌'의 좌표
        if(checkLocation(x, y - 1)) val += dfs(x, y - 1);

        return val;
    }
    public static boolean checkLocation(int x, int y){
        //좌표 값이 잘못된 경우
        if(x < 1 || x > n || y < 1 || y > n) return false;
        //이미 지나간 경로인 경우 || 집이 아닌 경우
        if(check[x][y] == true || arr[x][y] == 0) return false;
        return true;
    }
}