백준 | Python | DFS | 단지번호붙이기 (실버 1)

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

백준 2667번: 단지번호붙이기 - DFS/BFS 그래프 탐색 문제 풀이

단지번호붙이기(백준 2667번) 문제는 그래프 탐색(DFS/BFS) 알고리즘을 활용하여 지도에서 연결된 집들을 찾는 문제입니다.

 

이 문제를 통해 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 차이점을 이해하고,

적절한 탐색 방법을 선택하는 능력을 키울 수 있습니다.

---

📌 문제 이해

1️⃣ 문제 개요

N × N 크기의 지도에서 1(집)과 0(빈 공간)으로 이루어진 배열이 주어집니다.

이때, 연결된 집들(1)끼리 모여 하나의 "단지"를 형성하며,

각 단지의 개수와 단지 내 집의 수를 오름차순으로 정렬하여 출력하는 문제입니다.

 

연결된 집의 기준:

•   상, 하, 좌, 우로 연결된 경우 같은 단지로 간주
•   대각선 연결은 인정되지 않음

---

2️⃣ 입력 및 출력 예시

📌 입력 예시

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

📌 출력 예시

3
7
8
9

 

설명:

•   총 3개의 단지가 형성됨
•   각 단지 내 집 개수: [7, 8, 9]
•   오름차순 정렬 후 출력

---

📌 해결 방법: DFS vs BFS 선택하기

이 문제는 "연결된 집을 찾는 문제"로, 그래프 탐색 알고리즘인 DFS와 BFS를 모두 사용할 수 있습니다.

각 방법의 특징을 비교하여 어떤 방법이 적절한지 분석해 봅시다.

✅ DFS(깊이 우선 탐색) 풀이 방법

1. 2차원 배열을 탐색하면서 1(집)을 발견하면 DFS를 수행.
2. DFS를 통해 연결된 모든 집을 방문하면서 단지를 탐색.
3. 탐색이 끝나면 단지 개수를 증가시키고, 단지 내 집 개수를 저장.
4. 모든 탐색이 끝난 후, 단지 개수를 출력하고, 집 개수를 오름차순 정렬하여 출력.

-> DFS가 적합한 이유

✅ 연결된 모든 집을 끝까지 탐색한 후 돌아오는 방식이 단지를 찾는 방식과 일치

✅ 재귀(Recursion)를 사용하여 코드가 간결함

⚠️ 단점: 깊이가 깊어질 경우 스택 오버플로우 발생 가능

---

📌 DFS 코드 구현

import sys

sys.setrecursionlimit(10**6)  # 재귀 깊이 제한 해제

# 입력값 처리
input_data = sys.stdin.read().splitlines()
N = int(input_data[0])  # 지도 크기
graph = [list(map(int, list(row))) for row in input_data[1:N+1]]  # 지도 배열 변환

# 이동 방향 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# DFS 탐색 함수
def dfs(x, y):
    graph[x][y] = 0  # 방문 처리 (집을 0으로 변경)
    count = 1  # 현재 집을 포함하여 시작

    # 4방향 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
            count += dfs(nx, ny)  # 재귀 호출 시 count 값 누적

    return count  # 단지 내 집 개수를 리턴

# 단지 개수 및 각 단지 크기 저장 리스트
complex_sizes = []

# 모든 좌표 탐색
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:  # 집이 있는 경우 DFS 탐색 시작
            complex_sizes.append(dfs(i, j))  # 단지 크기 저장

# 결과 출력
print(len(complex_sizes))  # 총 단지 수 출력
for size in sorted(complex_sizes):  # 단지별 집 개수를 오름차순으로 출력
    print(size)

---

📌 BFS 코드 구현

✅ BFS(너비 우선 탐색) 풀이 방법

1. 2차원 배열을 탐색하면서 1을 발견하면 BFS를 실행.
2. BFS를 통해 연결된 모든 집을 큐에 넣고 하나씩 방문.
3. 방문한 집의 개수를 세고, 단지 개수를 증가.
4. 모든 탐색이 끝난 후, 단지 개수를 출력하고, 집 개수를 오름차순 정렬하여 출력.

BFS의 장점

✅ DFS보다 재귀 깊이 문제가 없어 안전

✅ 큐를 이용해 탐색 과정이 직관적

---

📌 BFS 코드

import sys
from collections import deque

# 입력값 처리
input_data = sys.stdin.read().splitlines()
N = int(input_data[0])
graph = [list(map(int, list(row))) for row in input_data[1:N+1]]

# 이동 방향 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque([(x, y)])
    graph[x][y] = 0  # 방문 처리
    count = 1  # 현재 단지 내 집 개수

    while queue:
        x, y = queue.popleft()

        # 4방향 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
                graph[nx][ny] = 0  # 방문 처리
                queue.append((nx, ny))
                count += 1  # 집 개수 증가

    return count

# 단지 개수 및 크기 저장 리스트
complex_sizes = []

# 모든 좌표 탐색
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:  # 집이 있는 경우 BFS 탐색 시작
            complex_sizes.append(bfs(i, j))

# 결과 출력
print(len(complex_sizes))
for size in sorted(complex_sizes):
    print(size)

---

📌 DFS vs BFS 비교

탐색 방식	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 순서	한 방향으로 끝까지 탐색 후 돌아옴	가까운 곳부터 탐색
사용 자료구조	재귀 호출 (스택) → 깊이 우선 탐색	큐 (deque) → 너비 우선 탐색
시간 복잡도	O(N²)	O(N²)
메모리 사용	재귀 호출로 인해 깊이가 깊어지면 스택 오버플로우 발생 가능	큐를 사용하므로 일정한 메모리 사용
속도	작은 입력에서는 빠를 수 있음	큰 입력에서도 안정적으로 동작

 

- DFS는 코드가 간결하지만, 깊이가 깊어질 경우 스택 오버플로우가 발생할 수 있음.

- BFS는 큐를 사용하여 탐색 과정을 더 명확하게 표현할 수 있음.

---

✅ 결론:

•   DFS는 코드가 간결하지만 깊이가 깊어질 경우 주의
•   BFS는 안정적으로 동작하여 추천