[크래프톤 정글 ] 백준 2178번 미로 탐색

2주차 에 접어들며 bfs 문제를 풀고 있다. 그중 미로 탐색 문제에 대한 정리 이다.

1. 문제 이해

• 목표: N×M 크기의 미로에서 시작점 (1, 1)에서 출발하여 도착점 (N, M)으로 이동하는 최단 경로를 찾는 것.
• 제약 조건:
  • 미로는 1과 0으로 구성되며, 1은 이동 가능한 경로, 0은 벽을 의미한다.
  • 서로 인접한 칸으로만 이동할 수 있다.
  • 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.
• 출력: 시작점에서 도착점까지 이동하기 위해 지나야 하는 최소 칸 수.

2. 접근법

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있다. BFS는 탐색 과정에서 가장 가까운 노드부터 탐색하므로, 최단 경로를 찾는 데 적합하다.

• BFS의 기본 개념:
  • BFS는 시작 노드에서 인접한 노드를 먼저 방문하고, 그다음에 그 노드들과 인접한 노드를 방문하는 방식으로 진행한다.
  • 큐(Queue)를 사용하여 탐색할 노드를 차례대로 처리한다.
  • 한 번 방문한 노드는 다시 방문하지 않도록 처리한다.

3. 구현 방법

구현 과정은 다음과 같다:

1. 입력 처리:
   • 첫 번째 줄에서 미로의 크기 N과 M을 입력받는다.
   • 이후 N개의 줄에 M개의 정수로 이루어진 미로 정보를 입력받아 2차원 리스트로 저장한다.
2. BFS를 이용한 최단 경로 탐색:
   • 시작점 (0, 0)에서 BFS를 시작한다.
   • 각 노드에서 상하좌우 인접 노드로 이동하며, 방문하지 않은 노드에 대해서 이동 거리를 기록한다.
   • 도착점 (N-1, M-1)에 도달하면 그 위치에 기록된 값이 최단 경로의 길이가 된다.
3. 큐(Queue) 사용:
   • 큐를 사용하여 현재 방문한 노드의 위치를 저장하고, 큐에서 꺼낸 노드의 인접 노드들을 탐색한다.
   • 인접한 노드가 이동 가능하고, 아직 방문하지 않았다면 그 노드를 큐에 추가하고, 이동 거리를 갱신한다.

4. 코드 구현

from collections import deque

def bfs(graph, start_x, start_y):
    # 상하좌우 이동을 위한 방향 정의
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 큐 초기화 (시작점 추가)
    queue = deque()
    queue.append((start_x, start_y))

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

        # 현재 위치에서 4방향으로 이동하면서 처리
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 미로 범위 밖으로 나가면 무시
            if nx < 0 or ny < 0 or nx >= len(graph) or ny >= len(graph[0]):
                continue

            # 0 인 경우 무시
            if graph[nx][ny] == 0:
                continue

            # 처음 방문하는 노드라면 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    # 도착지점의 최단 거리 반환
    return graph[-1][-1]

# 입력 받기
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().strip())))

# BFS를 수행하고 결과 출력
print(bfs(graph, 0, 0))

5. 시간 복잡도 분석

• BFS의 시간 복잡도는 O(V + E)이다. 여기서 V는 노드(칸)의 수, E는 간선(이동 가능한 경로)의 수이다.
• 이 문제에서는 V = N × M 이고, 각 노드에서 최대 4개의 방향으로 이동할 수 있으므로 E는 대략적으로 4 × V이다.
• 따라서, 이 문제의 시간 복잡도는 O(N × M)이다.

6. 핵심 포인트

• 입력이 인접 행렬 이라는 것을 빠르게 캐치 해야 한다.
• 미로의 각 칸에 도달할 때마다 그 칸까지의 최단 거리를 업데이트한다.
• 도착점에 도달했을 때의 거리가 바로 최단 경로의 길이가 된다.