[BFS, 파이썬] 백준 2178. 미로탐색 (최단거리)

별도 함수없이 while queue로 푼다.

보통 최단거리 구하는 문제는 BFS 를 쓰더라..!

• 좌표가 경로를 벗어나지 않는 범위 내에서 1. 방문여부 확인, 2. 길이 맞는지 확인.
• 조건에 맞다면 방문여부 표시하고, 큐에 넣어서 다음 차례에 추가.
• 방문 여부를 확인할 때, 방문 여부에 (이전 방문에 +1 함으로써) 몇 번째 방문인지 적기. 결국 마지막 좌표(목적지) 입력시 몇 번째 방문인지(거리)가 나오게 됨.

 

import sys
sys.stdin = open('C:\\tech\\backjoon\\graph\\input4.txt','r')
# 최단 거리

n,m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
# graph = [int(input().rstrip()) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

queue = [(0,0)]
visited[0][0] = 1 # 첫 시작

dx = [1,-1, 0, 0]
dy = [0, 0, 1, -1]

while queue:
    x, y = queue.pop(0)
    if x == n-1 and y == m-1: # 목적지
        print(visited[x][y])
        break
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m:
            if visited[nx][ny] == 0 and graph[nx][ny]==1:
                visited[nx][ny] = visited[x][y]+1 
                # 전에 방문했던 거에서 +1
                
                queue.append((nx,ny))