악곱 == 악성곱슬

DFS

---

해당 문제는 DFS, BFS 모두 사용가능하다

해당 문제에서 약간 까다로운 부분은 단지의 총 개수를 세는 것과, 각 단지별로 몇가구가 있는지 카운트 하는 부분이다.

이 부분은 python 구현 능력과 직결되는 부분이다.

global을 사용하여 구현하는 방법도 있지만 개인적인 취향(내 방식)에 따라 apt_n, cnt라는 인자를 전달하여 구현했다.

해당 문제는 입력이 2차원 배열 형태이므로 2차원 리스트로 그래프를 초기화 하여 구현했다.

import sys

def dfs(g, x, y, apt_n, cnt):
    # 인덱스 범위를 벗어났다면
    if x < 0 or y < 0 or x >= N or y >= N:
        return cnt
    # 이미 방문한 곳이거나 집이 없는 곳이라면
    if g[x][y] == 0 or g[x][y] > 1:
        return cnt
    # 아니라면 방문
    cnt += 1
    g[x][y] = apt_n
    cnt = dfs(g, x - 1, y, apt_n, cnt)
    cnt = dfs(g, x, y - 1, apt_n, cnt)
    cnt = dfs(g, x + 1, y, apt_n, cnt)
    cnt = dfs(g, x, y + 1, apt_n, cnt)
    return cnt

N = int(sys.stdin.readline().rstrip())
graph = list()
for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))
answer = 0
result = list()
apt_num = 2
count = 0
for i in range(N):
    for j in range(N):
        count = dfs(graph, i, j, apt_num, count)
        if count > 0:
            result.append(count)
            answer += 1
            apt_num += 1
            count = 0
print(answer)
result.sort()
for e in result:
    print(e)