[알고리즘 / 백준] 2667 - 단지번호붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

문제는 위와 같으며, 모든 아파트를 방문하였는지 확인하고 방문하지 않은 경우 주변 연관된 아파트들의 수를 확인하는 DFS 방식으로 문제를 해결할 수 있습니다.

 

예제를 살펴보면 아파트 위치와 방문했는지 여부를 확인하는 2차원 배열 2개를 생성합니다.

 

이후, 아파트 위치를 순차적으로 모두 확인하여 아파트가 있으면서 아직 아파트를 확인하지 않은 경우 dfs 메소드를 수행합니다.

 

이 dfs 메소드에서는 우선 현재 위치의 아파트를 확인했다는 표시로 +1 을 하고 상하좌우 4방향의 아파트 위치를 확인하여 해당 위치가 전체 범위내에 존재하고 해당 위치에 아파트가 있지만 아직 확인하지 않은 경우 이를 다시 dfs 메소드로 확인한 뒤, 그 값을 현재 위치의 확인(방

문) 횟수에 추가하도록 합니다.

 

첫번째 단지의 아파트를 확인하는 경우만 gif 로 살펴보겠습니다.

첫번째 단지 방문 시 연결된 아파트 확인

모든 위치의 아파트를 확인한 결과

 

이렇게 하면 현재 위치까지 연결된 아파트의 수를 모두 알 수 있고 이 값을 그대로 결과 배열에 넣은 뒤, 아파트 단지의 수를 +1 합니다. 최종적으로 아파트 단지의 수와 결과 배열을 정렬한 값을 순서대로 출력하면 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(cur_x, cur_y):
    visited[cur_x][cur_y] = 1  # 현재 위치 방문 값 +1
    for d in range(4):
        next_x = cur_x + dx[d]
        next_y = cur_y + dy[d]
        if 0 <= next_x < n and 0 <= next_y < n:  # 다음 위치가 범위 내에 존재하는 경우
            if visited[next_x][next_y] == 0 and apartments[next_x][next_y] != 0:  # 다음 위치를 아직 확인하지 않았고 다음 위치에 아파트가 존재하는 경우
                visited[cur_x][cur_y] += dfs(next_x, next_y)  # 현재 위치와 연결된 아파트 수에 다음 위치까지 연결된 아파트 수 추가

    return visited[cur_x][cur_y]  # 현재 위치와 연결된 아파트 수 반환


n = int(stdin.readline())
apartments = []
for _ in range(n):
    apartments.append(list(map(int, stdin.readline().strip())))  # 아파트 위치 입력 받기

visited = [[0] * n for _ in range(n)]  # 현 위치까지 연결된 아파트 수를 담을 배열
count = 0
result = []

# 전체 위치를 모두 돌면서 
for i in range(n):
    for j in range(n):
        if apartments[i][j] != 0 and visited[i][j] == 0:  # 아파트가 존재하지만 아직 확인하지 않은 경우
            result.append(dfs(i, j))  # 연결된 아파트 수를 확인하여 결과 배열에 넣고
            count += 1  # 아파트 단지 수 증가

print(count)
result.sort()  # 아파트 단지 내 아파트 수 오름 차순 정렬
for r in result:
    print(r)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {

    private static int n;
    private static int[][] apartments;
    private static int[][] visited;

    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        apartments = new int[n][n];
        for (int i = 0; i < n; i++) {
            apartments[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        }

        visited = new int[n][n];
        int count = 0;
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (apartments[i][j] != 0 && visited[i][j] == 0) {
                    result.add(dfs(i, j));
                    count++;
                }
            }
        }

        Collections.sort(result);
        for (int r : result) {
            sb.append(r).append("\n");
        }

        System.out.println(count + "\n" + sb);
    }

    private static int dfs(int x, int y) {
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < n) {
                if (visited[next_x][next_y] == 0 && apartments[next_x][next_y] != 0) {
                    visited[x][y] += dfs(next_x, next_y);
                }
            }
        }
        return visited[x][y];
    }
}