1. 문제 설명
- 문제 링크
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
조건
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
2. 풀이
- bfs를 활용하여 최단 거리 탐색
3. 코드
- python
from collections import deque
def bfs(x, y):
global N, M
q = deque() # x, y
q.append((x, y))
visited[x][y] = 1
while q:
# 첫 원소 꺼내기
x, y = q.popleft()
if x == N-1 and y == M-1:
print(visited[N-1][M-1])
break
# 상하좌우 탐색
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
# 맵 경계 벗어났으면 skip
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue
# 갈수 있는 길이면
if visited[nx][ny] == 0 and map[nx][ny] == 1:
# 다음 탐색 시점으로 입력
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
# 맵크기 입력
N, M = map(int, input().split())
# 맵정보 입력
map = [list(map(int,list(input()))) for _ in range(N)]
# 해당 위치까지 거리 저장
visited = [[0]*M for _ in range(N)]
# 상하좌우 이동
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 탐색실행 및 출력
bfs(0,0)
4. 결과
최단거리를 찾는 대표적인 문제