February 4, 2023

2667번: 단지번호붙이기

문제 요약

• 1과 0으로 이루어진 가로 세로 N의 정사각형 모양의 지도가 주어졌을 때, 1이 붙어있는 모임의 수와 각 모임에 몇 개의 1이 속하는지 출력
• 모임 내에 속한 1의 수는 오름차순으로 정렬하여 출력
• 5 ≤ N ≤ 25

풀이

from sys import stdin

input = stdin.readline

N = int(input())
home_list = [list(input()) for _ in range(N)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
result = []

def count_home(row, col):
    home_list[row][col] = '0'
    count = 0

    for direction_idx in range(len(dr)):
        nr = row + dr[direction_idx]
        nc = col + dc[direction_idx]

        if (nr >= 0 and nr < N and nc >= 0 and nc < N and home_list[nr][nc] == '1'):
            count += count_home(nr, nc) + 1

    return count

for row in range(N):
    for col in range(N):
        if (home_list[row][col] == '1'):
            result.append(count_home(row, col) + 1)

result.sort()

print(len(result))

for count in result:
    print(count)

• 지도를 순회하며, 각 칸이 1인 경우 인접한 1을 모두 방문처리하고 갯수 정보를 기록

시간 복잡도

• $O(N^3)$