[백준] 2667번 단지번호붙이기 (python 파이썬)

2667번: 단지번호붙이기

깊이우선탐색(dfs)로 해결

N = int(input()) # 지도의 크기 N 입력 받기

graph = []

for i in range(N):
    graph.append(list(map(int, input()))) # 0 or 1 입력 받기
    
# dfs 함수 정의하는 부분
# return은 [단지 내 아파트의 개수, 단지의 경우 True 반환]
def dfs(x, y, li):
    # 지도 범위를 벗어나면 안 되므로
    if x<=-1 or x>=N or y<=-1 or y>=N:
        return [0, False]
    
    # 1인 경우 아파트이므로 방문
    if graph[x][y]==1:
        # 여기서 li는 단지 내 아파트의 개수를 구하기 위해 사용됨
        li.append(1) # 아파트에 방문했으므로 li 리스트에 1을 저장
        
        graph[x][y]+=1 # 방문한 아파트는 2로 변경하여 재방문하지 않도록 함
        
        # 이동
        dfs(x-1, y, li)
        dfs(x+1, y, li)
        dfs(x, y-1, li)
        dfs(x, y+1, li)
        
        return [sum(li), True]
    else:
        return [0, False]
    
results = 0
temp=[] # li 와 같은 역할
count_list = [] # 단지의 개수를 리스트로 저장
for r in range(N):
    for c in range(N):
        
        sum_, bool_ = dfs(r, c, temp)
        
        if bool_==True:
            results += 1
            count_list.append(sum_)
        temp=[]

print(results)
count_list.sort() # 오름차순 정렬
for i in count_list:
    print(i)