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

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

 

def dfs(x, y, cnt, visited):
    # 방향 벡터 (상하좌우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    n, m = len(li), len(li[0])

    # 상하좌우 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        # 맵 범위를 벗어나지 않고, 이동 가능하며, 방문하지 않았을 때
        if 0 <= nx < n and 0 <= ny < m and li[nx][ny] == 1 and visited[nx][ny] == 0:
            visited[nx][ny] = cnt  # 방문 처리
            dfs(nx, ny, cnt, visited)

N = int(input())
li = [[0] * N for _ in range(N)]

for i in range(N):
    s = input()
    for j in range(N):
        li[i][j] = int(s[j])

visited = [[0] * N for _ in range(N)]
answer = list()
# 구역 수 세기
cnt = 0
# 다 돌면서 li가 1이고 visited가 0일 경우 dfs를 통해 구역 돌기
for i in range(N):
    for j in range(N):
        if li[i][j] == 1 and visited[i][j] == 0:
            cnt += 1
            visited[i][j] = cnt
            dfs(i, j, cnt, visited)

for c in range(cnt):
    cnt_one = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == c+1:
                cnt_one += 1
    answer.append(cnt_one)
answer.sort()

print(cnt)
구역에 따른 집의 수 오름차순 출력
for i in answer:
    print(i)