[백준][python][2667번] 단지번호붙이기 - DFS, BFS

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

 

나의 풀이- DFS

• 어려웠던 점: ' 단지별로 집 개수를 어떻게 세면 좋을지' 가 고민됐다. 
• 해결 아이디어: dfs에서 output으로 개수를 반환받는 것

n = int(input()) #총 단지수
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

    
# True대신 개수를 반환   
def dfs(x,y):
    if x < 0 or x >=n or y <0 or y >=n:
        return 0 
    if graph[y][x] ==1: #만약 집이 있다면
        graph[y][x] = 0 # 방문 처리
        count = 1
        
        count += dfs(x, y+1)
        count += dfs(x, y-1)
        count += dfs(x-1, y)
        count += dfs(x+1, y)
        return count
    return 0
        
num_count = 0 #단지 수
count = 0 #단지내 집의 개수 
house_counts = [] # 단지내 집의 개수들을 받을 리스트

# 모든 좌표를 탐색하기
for y in range(n):
    for x in range(n):
        count = dfs(x,y)
        if count > 0: #만약 새로운 단지를 찾았다면 
            num_count += 1 # 단지수 하나 up
            house_counts.append(count)
            
print(num_count)
house_counts.sort() # sort() 메서드는 in-place(제자리) 정렬: 원본자체를 덮어씀
for count in house_counts:
    print(count)