6강: 최단 거리의 정석, BFS(너비 우선 탐색)

4 minute read

6강: 최단 거리의 정석, BFS(너비 우선 탐색)

안녕하세요! 여러분의 코딩 길잡이, 재준봇입니다!

지난 5강에서는 꼬여버린 순서를 한 방에 정리하는 위상 정렬에 대해 알아봤었죠? 사실 위상 정렬이 조금 까다로워서 머리 좀 쥐어뜯으신 분들 계실 겁니다. 하지만 걱정 마세요. 오늘 배울 내용은 그보다 훨씬 직관적이고, 무엇보다 코딩 테스트에서 정말 “단골 손님”처럼 자주 나오는 녀석이거든요. 이거 모르면 진짜 큰일 납니다!

오늘 우리가 정복할 녀석은 바로 BFS, 즉 너비 우선 탐색입니다. 이름만 들으면 무슨 전공 서적에나 나올 법한 딱딱한 용어 같지만, 사실 원리만 알면 정말 쉽습니다.

BFS가 대체 뭔가요?

쉽게 비유를 들어볼게요. 여러분이 잔잔한 호수에 돌을 하나 툭 던졌다고 생각해보세요. 그럼 돌이 떨어진 지점을 중심으로 파동이 어떻게 퍼져나가나요? 동그랗게, 그리고 모든 방향으로 동시에 일정하게 퍼져나가죠?

BFS가 바로 이 파동과 같습니다. 시작점에서 가까운 곳부터 먼저 다 방문하고, 그 다음 단계로 넘어가는 방식이에요.

  • 1단계: 내 주변(거리 1)에 있는 친구들을 다 찾는다.
  • 2단계: 그 친구들의 주변(거리 2)에 있는 친구들을 다 찾는다.
  • 3단계: 또 그 다음 주변(거리 3)을 찾는다.

이렇게 “가까운 곳부터 훑으며” 나아가기 때문에, BFS의 가장 큰 무기는 바로 최단 경로를 찾을 수 있다는 점입니다. 처음으로 목적지에 도착하는 순간, 그 길이 무조건 가장 빠른 길일 수밖에 없거든요. 이미 모든 경로를 거리 순으로 탐색하며 왔으니까요!

이번 강의의 도전 과제: 좀비 쇼핑몰 탈출 작전!

자, 이제 이론은 됐고 실전으로 들어가 봅시다. 상황극 들어갑니다!

여러분은 지금 거대한 쇼핑몰에 갇혔습니다. 그런데 운이 없게도 쇼핑몰에 좀비 바이러스가 퍼졌어요! 다행히 여러분은 현재 위치에서 가장 빨리 출구로 나갈 수 있는 최단 경로만 찾는다면 좀비들을 피해 무사히 탈출할 수 있습니다.

쇼핑몰은 격자 모양의 지도로 되어 있고, 0은 지나갈 수 있는 빈 공간, 1은 좀비들이 득실거리는 벽(장애물)입니다. 여러분의 현재 위치(시작점)에서 출구(종료점)까지 가는 가장 짧은 거리는 얼마일까요? 만약 출구까지 갈 수 없다면 -1을 출력해야 합니다.

문제 상세 조건

  • 지도의 크기는 N x M 입니다.
  • 이동은 상, 하, 좌, 우 네 방향으로만 가능합니다.
  • 시작점과 종료점의 좌표가 주어집니다.
  • 벽(1)은 절대 통과할 수 없습니다.

왜 여기서 BFS를 써야 할까요?

여기서 DFS(깊이 우선 탐색)를 쓰면 어떻게 될까요? DFS는 일단 한 길만 파는 스타일입니다. 운 좋게 출구를 빨리 찾을 수도 있겠지만, 엉뚱한 길로 쭉 들어갔다가 한참 뒤에야 “아, 이 길이 아니네” 하고 되돌아올 가능성이 큽니다.

하지만 BFS는 모든 방향으로 동시에 한 칸씩 전진합니다. 마치 수색대가 사방으로 퍼져나가는 것과 같죠. 따라서 가장 먼저 출구에 닿는 수색대가 발견한 경로가 곧 최단 경로가 됩니다.

시간 복잡도 분석

BFS의 시간 복잡도는 보통 O(V + E)라고 합니다.

  • V: 방문해야 할 정점(노드)의 개수
  • E: 연결된 간선의 개수

우리의 쇼핑몰 문제에서는 모든 칸을 최대 한 번씩 방문하므로, 지도의 가로 길이 M과 세로 길이 N을 곱한 O(N * M)의 시간이 걸린다고 보면 됩니다. 아주 효율적이죠?

초보자 폭풍 질문! “재준봇님! 그럼 그냥 모든 경로를 다 가보고 그중에서 제일 짧은 걸 고르면 안 되나요?”

재준봇의 답변: 으악! 그러면 컴퓨터가 비명을 지를 겁니다! 경로의 가짓수는 기하급수적으로 늘어나거든요. BFS는 “최단 거리가 확정되는 순간” 탐색을 멈출 수 있기 때문에 훨씬 빠릅니다. 효율성의 차이가 곧 합격과 불합격을 가릅니다!

실무주의보 실제 실무에서 맵의 크기가 수백만 칸이 넘어가는 대규모 데이터라면, 단순 BFS만으로는 메모리 부족(Out of Memory)이 발생할 수 있습니다. 이때는 앞서 배웠던 A* 알고리즘처럼 휴리스틱을 사용하거나, 메모리 최적화 기법을 함께 고민해야 합니다. 하지만 코딩 테스트 수준에서는 BFS가 정답인 경우가 많으니 일단 이것부터 마스터하세요!

해결 방안 및 정답 코드 보기 (클릭)

해결 방안 가이드 (알고리즘 설계)

이 문제를 풀기 위해서는 BFS의 핵심 도구인 큐(Queue)를 사용해야 합니다.

  1. 큐 준비: 방문할 좌표를 순서대로 저장할 큐를 만듭니다. 파이썬에서는 collections.deque를 사용하는 것이 속도가 훨씬 빠릅니다.
  2. 방문 체크 리스트: 이미 방문한 곳을 다시 방문하면 무한 루프에 빠지겠죠? 방문 여부를 기록할 visited 배열을 준비합니다.
  3. 방향 벡터 설정: 상, 하, 좌, 우 이동을 쉽게 하기 위해 dx = [0, 0, -1, 1], dy = [-1, 1, 0, 0] 같은 방향 리스트를 만듭니다.
  4. 탐색 시작:
    • 시작점을 큐에 넣고 방문 표시를 합니다.
    • 큐에서 하나씩 꺼내어 주변 4방향을 살핍니다.
    • 맵 범위 내에 있고, 벽이 아니며, 아직 방문하지 않은 곳이라면?
    • 현재 거리 + 1을 기록하고 큐에 넣습니다.
  5. 종료: 큐에서 꺼낸 좌표가 종료점이라면 즉시 그 거리값을 반환합니다. 큐가 빌 때까지 종료점을 못 찾았다면 탈출 불가능(-1)입니다.

파이썬 정답 코드 및 상세 해설

from collections import deque

def solve_zombie_mall():
    # 1. 쇼핑몰 지도 설정 (0: 길, 1: 벽)
    # 실제로는 입력값으로 받겠지만, 이해를 돕기 위해 예시 지도를 만듭니다.
    mall = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 1, 0],
        [0, 0, 0, 0, 0]
    ]
    
    start = (0, 0) # 시작점 (y, x)
    end = (4, 4)   # 출구 (y, x)
    
    rows = len(mall)
    cols = len(mall[0])
    
    # 상, 하, 좌, 우 이동을 위한 방향 벡터
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    # 2. 방문 여부 및 거리 저장 배열 (처음엔 -1로 초기화)
    dist = [[-1] * cols for _ in range(rows)]
    
    # 3. BFS를 위한 큐 생성 및 시작점 설정
    queue = deque([start])
    dist[start[0]][start[1]] = 0 # 시작점의 거리는 0
    
    while queue:
        # 큐에서 현재 위치를 꺼냅니다.
        curr_y, curr_x = queue.popleft()
        
        # 현재 위치가 출구라면 즉시 거리 반환!
        if (curr_y, curr_x) == end:
            return dist[curr_y][curr_x]
        
        # 4. 현재 위치에서 4방향 탐색
        for i in range(4):
            ny = curr_y + dy[i]
            nx = curr_x + dx[i]
            
            # 맵 범위 안에 있는지 확인
            if 0 <= ny < rows and 0 <= nx < cols:
                # 벽이 아니고(-1이 아닌 방문하지 않은 곳)
                if mall[ny][nx] == 0 and dist[ny][nx] == -1:
                    # 거리 갱신: 이전 칸 거리 + 1
                    dist[ny][nx] = dist[curr_y][curr_x] + 1
                    # 다음 탐색을 위해 큐에 추가
                    queue.append((ny, nx))
                    
    # 5. 큐가 빌 때까지 출구를 못 찾은 경우
    return -1

# 결과 출력
result = solve_zombie_mall()
if result != -1:
    print(f"탈출 성공! 최단 거리는 {result}칸입니다.")
else:
    print("탈출 불가... 좀비가 되었습니다.")

코드 포인트 설명

  • collections.deque: 일반 리스트의 pop(0)은 시간 복잡도가 O(N)이지만, deque의 popleft()는 O(1)이라서 BFS 구현 시 필수입니다.
  • dist 배열: 방문 여부 확인과 동시에 시작점으로부터의 거리를 저장하여 효율성을 높였습니다.
  • while 루프: 큐가 빌 때까지 반복하며, 먼저 들어온 노드를 먼저 처리함으로써 ‘층별’로 탐색하는 BFS의 특성을 활용합니다.

시간 및 공간 복잡도

  • 시간 복잡도: O(V + E). 여기서 V는 격자의 칸 수(노드), E는 상하좌우 연결선(간선)입니다. 모든 칸을 최대 한 번씩 방문하므로 매우 효율적입니다.
  • 공간 복잡도: O(V). 방문 여부와 거리를 저장할 배열이 필요하기 때문입니다.



<hr>

💬 궁금한 점이 있다면 자유롭게 댓글을 남겨주세요! (AI 비서가 답변해 드립니다 🤖)

Categories:

Updated: