백준 2667 단지번호붙이기

문제

단지번호붙이기

연결되어 있는 단지에 번호를 붙이자

난이도 : Silver1

---

풀이

1. 집 탐색을 완료하면 0으로 변환
2. 모든 그래프가 0이 될 때까지 bfs로 단지 계산

---

코드

import sys
from collections import deque

N = int(sys.stdin.readline())
village = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
num_houses = []


def find_house(check_village):  # 집이 존재하면 해당 지점을 찾고, 없으면 끝내는 함수
    for i in range(N):
        for j in range(N):
            if check_village[i][j] == 1:
                return (i, j)

    return None  # 더 이상 탐색할 집이 없으면 None 리턴


def bfs(start_point):  # 단지를 묶고 한 단지에 속하는 집의 개수를 찾는 함수
    q = deque([start_point])
    village[start_point[0]][start_point[1]] = 0  # 탐색 지점 0으로 변환
    house = 1  # 단지 내 속하는 집 개수
    
    while q:
        i, j = q.popleft()
        for d in range(4):
            r = i + direction[d][0]
            c = j + direction[d][1]
            
            if 0 <= r < N and 0 <= c < N:
                if village[r][c] == 1:
                    q.append((r, c))
                    village[r][c] = 0
                    house += 1
    
    return house


def main(village):
    while True:  # 더 이상 탐색할 집이 없을 때까지 반복
        point = find_house(village)
        if point:
            num_houses.append(bfs(point))  # 한 지점에 대해 탐색이 완료되면 단지 내 아파트 개수 저장
        else:
            break
        
    print(len(num_houses))
    for i in sorted(num_houses):
        print(i)
    
main(village)