BOJ 2667. 단지 번호 붙이기 (Python)

BOJ 2667. 단지 번호 붙이기

2667번: 단지번호붙이기

Logic

1. DFS로 깊이탐색
2. 포문을 돌며 집인 경우에 깊이 탐색 시작.
3. dfs함수에선 집이 아닌경우 return하여 단지수인 count_apart +1 하도록 함
4. dfs함수에서 집인 경우 count_house[count_apart] +1 하여 집이 몇개인지 구함
5. 이후 집이 아닌 경우가 나올때까지 동서남북 깊이탐색
6. 단지수 print
7. 오름차순으로 정렬한 리스트가 0이 아닐 경우 print

Solution

from typing import List

def dfs(graph: List[List[int]], N:int, i:int, j:int, count_house: List, count_apart:int):
    # 더이상 집이 아닌 경우 return
    if i < 0 or i >= N or \
        j < 0 or j  >= N or \
            graph[i][j] <= 0:
            return

    # 집인 경우
    graph[i][j] = -1 # 구분하기 위함(방문)
    count_house[count_apart] += 1
    dfs(graph, N, i-1, j, count_house, count_apart)
    dfs(graph, N, i, j-1, count_house, count_apart)
    dfs(graph, N, i+1, j, count_house, count_apart)
    dfs(graph, N, i, j+1, count_house, count_apart)


# 입력
N = int(input())
graph = []
for i in range(0, N):
    graph.append((list(map(int, input()))))

count_apart = 0
count_house = [0]

for i in range(0, N):
    for j in range(0, N):
        if graph[i][j] > 0:
            dfs(graph, N, i, j, count_house, count_apart)
            count_apart += 1
            count_house.append(0)

filter(lambda x: x != 0, count_house)
count_house.sort()

# 출력
print(count_apart)
for n in count_house:
    if n != 0:
        print(n)

시간.. 메모리.. 안습