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

 

문제

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

 

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

 

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

 

---

 

사용한 클래스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ2667 {

    static Boolean[][] visited;
    static int[][] map;
    static int N, count;

    static int[] dx = new int[]{-1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, -1, 1};
    static List<Integer> result = new ArrayList<>();
    
    ...
}

 

• visited는 방문 여부를 위한 Boolean형 배열
• map은 아파트 단지를 인접행렬 형태로 입력 받을 int형 배열
• dx와 dy는 상하좌우 방향을 탐색을 위한 배열
  각 인덱스에 dx와 dy를 이용해 옆에 붙어있는 집을 찾는다.
  현재 위치가 (1,2)라면 (2,2), (0,2), (1,3), (1,1)을 탐색
• count와 result는 최종 출력을 위해 선언하였다.

 

 

DFS

static void DFS(int x, int y){
        visited[x][y] = Boolean.TRUE;

        // x, y로 양방향 탐색
        for (int i = 0; i < 4; i++) {
            // 상하좌우로 다른 집이 있는지 찾기 위해 dx, dy를 사용
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            // 0과 N은 탐색 범위를 벗어나지 않게 제한을 두는 것
            //범위에 벗어나지 않고 탐색 조건에 맞으면 DFS 탐색
            if (new_x>=0 && new_y>=0 && new_x<N && new_y<N && !visited[new_x][new_y] && map[new_x][new_y]==1){
                DFS(new_x, new_y);
                count++;
            }
        }
    }

 

방문한 위치의 visited를 True로 변경하고 양방향을 탐색한다.
지도의 크기는 0부터 N까지 → 이 범위를 벗어나지 않기 위해 0보다 크거나 같고, N보다 작은지 확인
옆의 인덱스를 방문하지 않았고, 해당 인덱스에 집이 있으면 (값이 1이면) DFS 탐색

각 단지마다 집의 수를 세기 위해 count를 증가시켜준다.

 

 

메인 메서드

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

        map = new int[N][N];
        visited = new Boolean[N][N];

//	# 1.
        for (int i = 0; i < N; i++) {
            String[] temp = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(temp[j]);
                visited[i][j] = Boolean.FALSE;
            }
        }


//	# 2.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count = 0;

                // 해당 위치에 건물이 있고, 방문하지 않았으면 DFS 탐색
                if (map[i][j]==1 && !visited[i][j]){
                    DFS(i,j);
                    count++;
                    result.add(count);
                }
            }
        }


        // 총 단지 수
        System.out.println(result.size());

        // 각 단지내 집의 수 + 오름차순 정렬
        Collections.sort(result);
        Iterator i = result.iterator();
        while(i.hasNext())
            System.out.println(i.next());

    }

 

# 1.
split()을 이용해 한글자씩 배열에 집어넣어
map의 각 인덱스에 넣어주면서 visited의 초기화를 함께 해준다.

 

# 2.
count는 각 단지의 집의 개수를 세어줄 변수 → 0으로 초기화
result는 count를 모아두기 위한 최종 출력 리스트

해당 인덱스에 건물이 있으면 값이 1이고, 건물이 없으면 값이 0
map[i][j]가 1이고 (집이 있고), visited가 False인 (방문하지 않은) 위치를 DFS로 탐색한다.

 

# 3.
총 단지의 수는 result.size()로 가져오고
Iterator를 통해 result 안에 있는 요소를 하나씩 가져와 출력한다.

문제 조건: 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력
을 맞추기 위해 Collections.sort(List)로 오름차순 정렬을 해주었다.