CHAPTER 2. 탐색 & 탐색 알고리즘 (격자, BFS, DFS)

본 챕터에서는 코딩테스트 탐색 문제의 80% 이상을 차지하는 격자(2D 배열) 탐색, BFS(너비 우선 탐색), DFS(깊이 우선 탐색)의 핵심 원리와 필수 템플릿 코드를 다뤄보고자 한다.

 

2-1. 격자 탐색 & 방향 벡터

2차원 배열 grid에서 상,하,좌,우로 이동할 때 x, y 축 좌표 변화를 테크닉화한 것임.

 

1. 방향 벡터 가산 원리 (dx, dy) 

행(row)을 x, 열(column)을 y라 할 때, 4방향 이동 시 변동되는 좌표값을 리스트로 미리 선언함.

# 상, 하, 좌, 우 (순서는 상관없으나 쌍을 맞춰야 함)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 현재 위치 (x, y) = (2, 2)일 때 4방향 다음 위치(nx, ny) 구하기
x, y = 2, 2

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    print(f"방향 {i}: ({nx}, {ny})")

• [상, 하, 좌, 우]의 경우 위로가는건 -1, 아래로가는건 +1, 좌로가는건 -1, 우로가는건 +1으로 고정한다.
• 이때 dx는 '상, 하' 만 다루기 때문에, '좌, 우'에 해당하는건 0, 0임 - [-1, 1, 0, 0]
• 동일한 원라로 dy는 '좌, 우' 만 다루기 때문에, '상, 하'에 해당되는건 0,0임 - [0, 0, -1, 1]
• nx와 ny는 현재의 위치를 나타내며, i값에따라 바뀐다. 
  • i=0: (1,2)
  • i=1: (3,2)
  • i=2: (2, 1)
  • i=3: (2, 3)

 

2. N * M 배열 범위 검사 (필수!)

격자 밖으로 벗어나는 인덱스 에러(IndexError)를 방지하기 위해 이동 직후 반드시 범위를 검사해야 함.

N, M = 5, 5  # 5x5 격자 (0~4 인덱스)

if 0 <= nx < N and 0 <= ny < M:
    # 격자 내부일 때만 안전하게 이동 및 로직 수행
    pass

 

2-2. BFS (너비 우선 탐색, Breadth-First Search)

출발점으로부터 동심원 물결처럼 사방으로 1단, 2단 퍼져나가는 탐색.

 

1. 핵심 원리 & 사용 목적 

핵심 자료구조: 선입선출(FIFO)인 deque (큐) 

언제 쓰는가?: "최단거리", "최소 이동 횟수", "가장 빠르게 도달하는 경로" 문제

 

2. BFS 최단거리 기본 템플릿

from collections import deque

def bfs(startX, startY, N, M, grid):
    # 상, 하, 좌, 우 방향 벡터
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 1. 큐 생성 및 시작점 삽입
    queue = deque([(startX, startY)])
    
    # 2. 큐가 빌 때까지 반복 탐색
    while queue:
        x, y = queue.popleft()  # O(1) 속도로 꺼냄
        
        # 4방향 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 격자 범위를 벗어나면 건너뛰기
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
                
            # 벽(0)이거나 이미 방문한 곳이면 건너뛰기
            if grid[nx][ny] == 0:
                continue
                
            # 처음 방문하는 길(1)인 경우
            if grid[nx][ny] == 1:
                # 이전 위치 거리 + 1 을 통해 최단거리 누적 기록!
                grid[nx][ny] = grid[x][y] + 1
                queue.append((nx, ny))
                
    # 도착지 (N-1, M-1)의 최단거리 반환
    return grid[N-1][M-1]

 

2-3. DFS (깊이 우선 탐색, Depth-First Search)

갈 수 있는 한 우물을 막다른 길이 나올 때까지 끝까지 파고들었다가 되돌아오는(백트래킹) 탐색.

 

1. 핵심 용어 및 구조

 

• Vertex (v): 정점(노드 / 방 번호).
• Graph: 간선(Edge) 연결 정보를 담은 지도.
• Visited: 가본 정점인가 체크하는 출석부 배열 ([False] * (노드수 + 1)).
• 언제 쓰는가?: "모든 경우의 수 탐색", "조합 구하기", "목적지까지 가는 경로 존재 여부" 문제

2. DFS 기본 재귀 템플릿

# graph: 노드 연결 지도, v: 현재 노드 번호, visited: 방문 출석부
def dfs(graph, v, visited):
    # 1. 현재 노드 방문 처리 (도장 쾅!)
    visited[v] = True
    print(v, end=' -> ')  # 방문 순서 확인용
    
    # 2. 현재 노드와 간선(Edge)으로 연결된 인접 노드들 확인
    for neighbor in graph[v]:
        # 아직 가보지 않은 노드라면 깊숙이 파고들기 (재귀 호출)
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

# --- 실제 실행 예시 ---
# 0번은 안 쓰고 1~4번 노드 사용 (크기 5짜리 백화점 출석부)
visited = [False] * 5

# 1번 노드는 [2, 3]과 연결, 2번은 [1, 4]와 연결 ...
graph = [
    [],        # 0번 (미사용)
    [2, 3],    # 1번 노드
    [1, 4],    # 2번 노드
    [1],       # 3번 노드
    [2]        # 4번 노드
]

# 1번 노드부터 깊이 탐색 시작!
print("DFS 방문 순서:")
dfs(graph, 1, visited)
# 출력 결과: 1 -> 2 -> 4 -> 3 ->