[백준 2178번] 미로 탐색

[백준 2178번] 미로 탐색

• 문제 링크 : 미로 탐색
• 난이도 : 실버 1
• 풀이 날짜 : 2025-02-10

---

📖 문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

📌 입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

📌 출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

⌨️ 예제 입출력

입력

4 6
101111
101010
101011
111011

출력

15  

---

📝 풀이 코드

from collections import defaultdict, deque
from queue import PriorityQueue
import sys
import math
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N, M = map(int,input().split()) # 배열 크기(x,y)
A = [[0] * M for _ in range(N)] # 좌표 리스트 초기화
visited = [[False] * M for _ in range(N)] # 방문 기록


# 좌표 리스트에 데이터 넣기
for i in range(N):
    numbers = list(input())
    for j in range(M):
        A[i][j] = int(numbers[j])

# 이동 방향 (상, 하, 좌, 우) 정의
dx = [-1, 1, 0, 0]  # x 좌표 이동 (위, 아래)
dy = [0, 0, -1, 1]  # y 좌표 이동 (왼쪽, 오른쪽)

# BFS 탐색 함수 정의
def bfs(x, y):
    queue = deque()  # BFS를 위한 큐 초기화
    queue.append((x, y))  # 시작 좌표 삽입
    visited[x][y] = True  # 방문 처리

    while queue:
        now = queue.popleft()  # 현재 위치 꺼내기

        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            # 미로 범위를 벗어나지 않는지 체크
            if nx >= 0 and ny >= 0 and nx < N and ny < M:
                # 이동할 수 있는 칸(1)이고 방문하지 않았다면
                if A[nx][ny] != 0 and not visited[nx][ny]:
                    visited[nx][ny] = True # 방문 처리 
                    A[nx][ny] = A[now[0]][now[1]] + 1 # 이동 거리 업데이트
                    queue.append((nx, ny)) # 큐에 삽입


bfs(0,0)

# (N-1, M-1) 좌표에 기록된 최단 거리 출력
print(A[N-1][M-1])

---

🔍 코드 설명

• 미로 탐색 문제를 해결하기 위해 BFS(너비 우선 탐색)를 사용
• 최단 거리를 구해야 하므로 DFS보다 BFS가 적절
• 큐(Queue) 사용 한 단계씩 이동하며 최단 거리 갱신
• 방문 여부 visited 로 체크
• 마지막 칸 (N-1, M-1)에 도착했을 때 최단 거리 출력