[BOJ / Python] 14940번: 쉬운 최단거리

문제: BOJ 14940번

풀이

벽 부수고 이동하기 시리즈 시작편이라고 해야되나...?? 암튼 최단경로 찾기 문제이다. BFS로 2인 지점에서부터 탐색을 시작하면 된다.
갈 수 없으면 -1 로 하는 것이 관건일 것 같은데, 그냥 거리 배열을 -1로 초기화하고 2인 부분을 0,
0인 부분을 0으로 초기화시키고 -1인 부분만 바꾸면 되게 하는게 좋을 것 같다.

최종코드

import sys
from collections import deque
input=sys.stdin.readline
d=[[0,1],[0,-1],[-1,0],[1,0]] #사방을 탐색하기 위한 상수

n,m=map(int,input().split())
ar=[]
for i in range(n):  
    ar.append(list(map(int,input().split())))
vis=[[-1 for _ in range(m)]for _ in range(n)] #-1로 초기화한다.

for i in range(n):	#2인 위치를 찾고 0인 값은 방문배열에서도 0으로 세팅한다.
    for j in range(m):
        if ar[i][j]==2:
            a,b=i,j
        if ar[i][j]==0:	
            vis[i][j]=0
vis[a][b]=0		#2인 위치는 도착점이므로 0으로 초기화
	
def bfs():		#BFS함수
    q=deque()			
    q.append((a,b))
    while q:
        x,y=q.popleft()
        for xx,yy in d:		
            nx=x+xx
            ny=y+yy
            if nx<0 or ny<0 or nx>=n or ny>=m: #범위를 벗어나면 건너뛰기
                continue		
            if ar[nx][ny]==1 and vis[nx][ny]==-1:	#0이 아니고 방문 아직 안헀다면
                vis[nx][ny]=1+vis[x][y]	#이전 위치의 거리에서 +1 해준다.
                q.append((nx,ny))	#큐에 추가
bfs()		#호출

for i in range(n):	#형식에 맞춰 출력
    for j in range(m):
        print(vis[i][j],end=' ')		
    print()