[BOJ] 2667. 단지번호붙이기 (Python/DFS/Silver 1)

[Baekjoon] 2667. 단지번호붙이기

Silver 1 | #DFS #그래프탐색

문제 바로가기 🔗

1. 문제 요약

정사각형 모양의 지도에서 1(집이 있는 곳)이 상하좌우로 연결된 그룹(단지)을 찾고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제이다.

2. 문제 풀이 방식

• DFS(깊이 우선 탐색): 지도를 순회하며 1을 발견하면 DFS를 시작한다.
• 방문 처리: 탐색한 집은 다시 방문하지 않도록 0으로 값을 변경한다.
• 상하좌우 이동: dx, dy 배열을 활용해 인접한 좌표를 탐색한다.

3. 전체 코드 (Python)

import sys
input = sys.stdin.readline

N = int(input())
graph = [list(map(int, input().strip())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

home = [] # 각 단지의 집 수를 담을 리스트

def dfs(i, j):
    cnt = 1 # 현재 위치의 집 카운트
    graph[i][j] = 0 # 방문 처리
    
    for k in range(4):
        nx, ny = i + dx[k], j + dy[k]
        
        # 지도 범위 내에 있고, 아직 방문하지 않은 집(1)인 경우
        if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
            # 재귀적으로 탐색하며 반환된 집의 수를 현재 cnt에 누적
            cnt += dfs(nx, ny)
            
    return cnt

# 지도를 전체 순회하며 단지 탐색
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            home.append(dfs(i, j))

# 결과 출력
print(len(home)) # 단지 수
for i in sorted(home): # 오름차순 정렬 조건 필수
    print(i)

4. ✍️ 회고: 시행착오와 성장 기록

🚫 시행착오: 매개변수와 리턴값의 함정

초기 풀이에서 cnt를 매개변수로 넘겼으나, 파이썬의 정수(int)는 불변(immutable) 타입이라 재귀 호출 후의 변경 사항이 부모 함수에 반영되지 않았다. 또한 cnt += dfs(nx, ny)처럼 반환값을 누적하지 않아 데이터가 유실되었다. 이를 해결하며 재귀 구조에서의 데이터 흐름을 명확히 이해하게 되었다.

---

✔ BFS에서 DFS로: 도구를 선택하는 기준

과거 풀이(#163)에서는 단순히 익숙한 BFS(큐)를 사용했었다. 하지만 이번에 DFS(재귀)를 선택하며 상황에 맞는 알고리즘 기준을 세울 수 있었다.

• • BFS(과거): 큐 선언이 필요하고 단계별 탐색에 유리하지만, 이 문제처럼 단순 영역 크기 계산엔 코드가 다소 길어진다.
• • DFS(현재): 재귀의 반환값을 이용해 별도 자료구조 없이도 영역 크기를 훨씬 컴팩트하게 산출 가능하다.
• • 결론: 최단 거리 탐색은 BFS, 연결된 영역의 크기 판별은 DFS가 더 효율적임을 체득했다.

---

💡 마무리 포인트

• 별도의 area 변수 없이 리스트 길이(len(home))로 단지 수를 반환해 코드를 간결화했다.
• 문제의 조건(오름차순 정렬 출력)을 다시 한번 확인하는 습관을 들였다.