문제 이해
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)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
즉 1,1부터 N,M까지 가는 거리의 최단거리를 구하는 문제이다.
문제 분석
사실 이런 형태의 문제는 BFS의 기본이라고 볼 수 있다.
오른쪽,왼쪽,위,아래를 모두 확인하고 방문하지 않았더라면 현재까지의 거리 + 1으로 거리를 표시해두면 우리가 최종적으로 도착해야 하는 N,M에 최단거리가 들어있을 것이다.
문제 풀이
시작점 0,0을 queue에 넣어두고 시작한다.
0,0 에서 상하좌우를 모두 확인한다. 이때 상하좌우에서 pan이 1, 즉, 지나갈 수 있는 통로이고 visited 방문한적이 없다면 queue에 그 좌표를 넣어준다. 그리고 거리를 1 증가시킨다.
이를 반복하다보면 최종적으로 N-1,M-1에 도착하게 된다. 그 때의 distance[N-1][M-1]이 최단거리가 되는 것이다.
dx = [0,0,-1,1]
dy = [-1,1,0,0]
def bfs():
queue = deque()
queue.append((0,0))
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny < 0 or nx>=N or ny >= M:
continue
if visited[nx][ny]==False and pan[nx][ny] == '1':
queue.append((nx,ny))
visited[nx][ny] = True
distance[nx][ny] += distance[x][y]제출 코드
from collections import deque
import sys
N,M = map(int, sys.stdin.readline().split())
pan = [list(str(sys.stdin.readline().strip())) for _ in range(N)]
visited = [[False for _ in range(M)] for i in range(N)]
distance = [[1 for _ in range(M)] for i in range(N)]
dx = [0,0,-1,1]
dy = [-1,1,0,0]
def bfs():
queue = deque()
queue.append((0,0))
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny < 0 or nx>=N or ny >= M:
continue
if visited[nx][ny]==False and pan[nx][ny] == '1':
queue.append((nx,ny))
visited[nx][ny] = True
distance[nx][ny] += distance[x][y]
bfs()
print(distance[N-1][M-1])
