[백준] 2667번 - 단지번호붙이기

문제링크 : www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

지도와 동일한 크기를 가지는 visited리스트를 만든다. visited는 방문했으면 True, 방문하지 않았으면 False값을 가진다. 따라서 map이 '1'값을 가지고, visited가 False값을 가질 때 탐색을 시작하도록 한다. 탐색한 부분의 visited는 True로 변경하고, 상하좌우 중 map이 '1'값을 가지고 visited가 False인 지점이 있으면 재귀를 이용하여 탐색을 진행한다.

import sys
sys.setrecursionlimit(10**9)

house_num = 0
house_nums = []
def dfs(house_map, visited, start_row, start_col):
    if visited[start_row][start_col]:
        return

    global house_num

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

    house_num += 1
    visited[start_row][start_col] = True

    for i in range(len(dx)):
        if 0 <= start_row + dy[i] < len(house_map) and 0 <= start_col + dx[i] < len(house_map[start_row+dy[i]]):
            if house_map[start_row+dy[i]][start_col+dx[i]] == '1' and not visited[start_row+dy[i]][start_col+dx[i]]:
                dfs(house_map, visited, start_row+dy[i], start_col+dx[i])


N = int(sys.stdin.readline())

house_map = [sys.stdin.readline().rstrip() for _ in range(N)]
visited = [[False] * N for _ in range(N)]

group_count = 0
for i in range(len(house_map)):
    for j in range(len(house_map[i])):
        if house_map[i][j] == '1' and not visited[i][j]:
            dfs(house_map, visited, i, j)
            group_count += 1

            if house_num != 0:
                house_nums.append(house_num)
                house_num = 0

print(group_count)

house_nums.sort()
for house_num in house_nums:
    print(house_num)