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

풀이

이코테 음료수 얼려먹기 문제와 똑같다고 봐도 무방
집은 1 집이 없는 곳은 0, 상하좌우로 붙어있는 같은 단지의 집은 같은 번호로 방문체크하면서 bfs수행
True를 반환할 때마다 증가하는 answer(단지의 개수)를 이용해서 딕셔너리를 만들고 집을 방문 처리할 때 마다 해당 단지(key)의 값을 1 증가시킨다.
(각 단지에 속한 집의 개수를 출력해야 하는데, bfs 끝나고 for문 다시 돌리는 것은 비효율적인것 같아서 이렇게 구현하였다.)

코드

import sys
input = sys.stdin.readline
n = int(input())
maps = []
for _ in range(n):
    maps.append(list(map(int,input().rstrip())))

# 단지의 집의 수 체크
danji = {}
def dfs(x, y):
    global answer
    # 범위를 넘어가면 안됨
    if x<0 or y<0 or x>=n or y>=n:
        return False
    # 각 단지의 숫자로 방문 처리
    if maps[y][x]==1:
        maps[y][x]=answer
        try:
            danji[answer] +=1
        except:
            danji[answer] = 1
        # 해당 집의 상하좌우에 이어지는 집 탐색
        dfs(x,y+1)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x-1,y)
        return True
    return False
# 집 없음 0, 집을 나타내는 숫자가 1이므로 단지는 2부터 시작
answer = 2

for i in range(n):
    for j in range(n):
        if dfs(j,i) == True:
            answer+=1
print(answer-2)
for i in sorted(danji.values()):
    print(i)