BOJ-2667 단지번호붙이기

https://www.acmicpc.net/problem/2667

문제 소개

정사각형 모양의 지도의 크기 n과 지도가 주어진다. 지도에서 1은 집이 있는 곳이고, 0은 집이 없는 곳이다.

좌우 혹은 아래위로 연결된 집의 모임을 단지라고 했을 때, 총 단지의 수와 각 단지내 집의 수를 오름차순으로 정렬하여 출력한다.

문제 풀이

dfs로 풀이하였다. 지도의 칸을 하나씩 검사하며 방문하지 않았다면 해당 칸에서부터 dfs로 단지를 탐색한다.

함수 dfs에서는 한 칸을 탐색할 때마다 해당 단지 내 집의 개수인 cnt_house를 1 증가시킨다. 단지 하나를 모두 탐색하면 단지의 개수인 cnt를 1 증가시키며, cnt_house를 cnt_house_list에 추가한다.

dx와 dy는 dfs에서 상하좌우에 인접한 칸에 접근하기 위한 값으로 dfs내부에서 반복문으로 접근한다.

마지막으로 cnt를 출력하고 이어서 cnt_house_list를 정렬 후 하나씩 출력한다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

# 좌, 상, 우, 하 순서
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


def dfs(x, y):
    global cnt_house
    arr[x][y] = 0
    cnt_house += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= n - 1 and 0 <= ny <= n - 1 and arr[nx][ny]:
            dfs(nx, ny)


n = int(input())
arr = [list(map(int, list(input()))) for _ in range(n)]

cnt = 0
cnt_house_list = []

for i in range(n):
    for j in range(n):
        if arr[i][j]:
            cnt_house = 0
            dfs(i, j)
            cnt += 1
            cnt_house_list.append(cnt_house)

# 출력
print(cnt)
cnt_house_list.sort()
for i in cnt_house_list:
    print(i)