[알고리즘] 백준 2667 단지번호붙이기 - 파이썬

오늘은 백준의 단계별 풀어보기에서 DFS와 BFS단계 단지 번호 붙이기 문제를 풀어보았습니다.

 

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

2667번: 단지번호붙이기

 

 

풀이 코드

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

graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

cnt = 0 # 단지내 집의 수 카운트
cnt_list = [] # 하나의 단지내 집의 수를 담을 리스트

#dfs, 스택, 재귀
def dfs(x, y):
    global cnt
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False

    if graph[x][y] == 1:
        cnt += 1 # 집인경우 +1
        graph[x][y] = 0 # 탐색한 것은 0으로 변경(원활한 재귀 종료를 위함)
        dfs(x-1, y) # 상
        dfs(x+1, y) # 하
        dfs(x, y-1) # 좌
        dfs(x, y+1) # 우
        return True
    return False

result = 0
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            result += 1
            cnt_list.append(cnt)
            cnt = 0

cnt_list.sort() # 지문에 오름차순 요구
print(result) # 단지 수 출력
print(*cnt_list, sep='\n') # 리스트의 요소를 하나씩 줄바꿈하여 출력

 

문제풀이

: 이번 문제의 연결된 집을 따라 단지수를 출력해야 한다는 지문을 보고 '1'인 지점부터 상하좌우로 재귀 문을 활용한다면 단지 수를 쉽게 출력할 수 있을 거라 생각했습니다. 단지 수를 출력하는 것까지는 이전 문제들과 비슷하여 쉽게 풀었지만 각 단지 내 집의 수를 출력하는 부분에서 막혀 함수 내에 전역 변수를 로드할 수 있는 global을 활용했습니다.

출력 부분에서 집의 수를 오름차순으로 정렬해야 한다는 부분을 깜빡해서 sort()를 깜빡했는데 실전에서 이런 사소한 부분을 놓치면 아찔했을 것 같습니다.. 코드에 대한 설명은 주석을 달아놨습니다.