백준 2175번 미로탐색

bfs로 최단거리를 찾는 문제인데 이전문제들과 달리 시작점이 정해져서 탐색을 시작한다 그점을 기준으로 노드마다 최단거리를 구해서 그 값을 노드에 저장한다

노드에는 최단거리가 저장되고 그 다음 노드는 이전 노드의 값에 +1 을해서 값을 저장한다 그리고 첫번째 노드는 1의 값을 가지고 있으면 재탐색 될 수 있기 때문에 값을 바꿔줘야한다

from collections import deque
import sys
input = sys.stdin.readline

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

line = [] #입력받은 값을 저장할 리스트
cnt = 1 #시작점
q =deque() #bfs를 위한 큐

n,m = map(int,input().split()) 

for _ in range(n):
    line.append(list(map(int,str(input())[:-1] ))) #띄어쓰기 없이 입력받은 숫자를 하나씩 분리해서 2중 리스트에 저장

q.append([0,0]) # 고정된 시작점


while q:
    x,y = q.popleft()
    for i in range(4):# 탐색을 통해 움직일 수 있는 방법 4가지
        a = x+dx[i]
        b = y+dy[i]
            
        if a<0 or b<0 or a>=n or b>=m:
            continue
        if line[a][b] == 1:
            q.append([a,b])
            line[a][b] = line[x][y] + 1
        
    
    line[0][0] = 5 # 초기값 재탐색을 방지하기 위해 처음값을 1 이외로 저장시켜야 한다
        
            
print(line[n-1][m-1]) #마지막 노드의 저장된 값을 출력한다