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

문제설명

• 기본적인 아래와 같은 DFS 문제와 거의 유사하지만 추가해야 하는 조건이 있다.

2021.03.14 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] [우선탐색] DFS와 BFS 1260 (파이썬)

[백준] [우선탐색] DFS와 BFS 1260 (파이썬)

스케치

코드

# 단지 번호 붙이기
def dfs(x,y):
    global temp
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False    # 주어진 범위를 벗어나면 즉시 종료
    if graph[x][y] == 1:
        graph[x][y] = 0 # 집이 없는 곳인 0으로 바꿔서 방문처리를 한다.
        temp += 1 # 단지내 아파트 수를 위한 임시 카운트

        # 상하좌우에 대해서 dfs 탐색
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False

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

graph = [] # 지도 그리기
for _ in range(n):
    graph.append(list(map(int,input())))

result = 0 # 아파트 단지 수
count_list = [] # 단지별 아파트 수를 갖는 배열
temp = 0

for i in range(n):
    for j in range(n):
        if dfs(i,j) == True: # 한동을 다 돌았다. 
                result += 1
                count_list.append(temp) # dfs 탐색이 끝났다면 단지내 아파트수 (temp)를 count_list에 append 후 temp 초기화
                temp = 0

print(result)

count_list.sort() # 단지내 집의 수를 오름차순으로 정렬
for count in count_list:
    print(count)