문제

입력

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

출력

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

입력 예시 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

출력 예시 1

3
7
8
9

문제 이해

그냥 상하좌우로 연결되어 있는 요소가 총 몇개인지 구하는 문제인데, 거기서 각각의 한 덩어리가 몇개의 요소로 이루어져있는지도 카운트 해주면 된다.

코드 및 설명

# 백준 2667번 단지번호붙이기

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def DFS(y, x):
    global maps, visited, count
    visited[y][x] = True
    count += 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and maps[ny][nx] and not visited[ny][nx]:
            DFS(ny, nx)

# 0. 입력 및 초기화
N = int(input())
maps = []
visited = [[False] * N for _ in range(N)]

cnt_lst = []
answer = 0

# 1. 연결 요소 입력
for i in range(N):
    maps.append(list(map(int, input().rstrip())))

# 2. DFS 호출
for i in range(N):
    for j in range(N):
        if maps[i][j] and not visited[i][j]:
            count = 0
            DFS(i, j)
            cnt_lst.append(count)

            answer += 1

# 3. 오름차순 정리
cnt_lst.sort()

# 4. 출력
print(answer)
for i in range(len(cnt_lst)):
    print(cnt_lst[i])

카운트는 한덩어리에 몇개가 있는지 카운트 해주면 된다. 그리고 한덩이는 메인에서 한번 호출하면 그게 한덩어리다. 그렇다면 메인에서 DFS를 호출하기 전에 count를 0으로 초기화 하고 호출후에 cnt값을 다른 리스트에 넣어준다. 그리고 메인에서 DFS호출이 끝나면 answer를 증가시켜서 몇개의 덩어리인지도 카운트 해준다.