[코드트리] 마을 구분하기 Python

# n 입력
n = int(input())
# towns 입력
towns = [
    list(map(int, input().split()))
    for _ in range(n)
]

# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# is_connected(x, y)
def is_connected(x, y):
    # 범위 내에 있고, 방문한 적 없고, 사람이면 가능
    return in_range(x, y) and not visited[x][y] and towns[x][y]

# dfs(x, y)
def dfs(x, y):
    # 전역 변수 선언
    global ppl

    # dxs, dys
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        # 이어져 있으면
        if is_connected(nx, ny):
            # ppl 올려주고
            ppl += 1
            # 방문 처리 후
            visited[nx][ny] = True
            # dfs
            dfs(nx, ny)

# 설계
# visited
visited = [
    [0] * n
    for _ in range(n)
]

# town_list
town_list = []

# 마을을 돌면서
for i in range(n):
    for j in range(n):
        # 사람이 있고, 방문한 적 없으면
        if towns[i][j] and not visited[i][j]:
            
            # ppl
            ppl = 1

            # 방문 처리 해 주고
            visited[i][j] = True
            # dfs -> 인원 수 올려주기
            dfs(i, j)

            # town_list에 추가
            town_list.append(ppl)

# town_list 정렬
town_list.sort()

# 출력
print(len(town_list))
for ppl_num in town_list:
    print(ppl_num)