[백준 파이썬] 14940 쉬운 최단거리

📌문제 출처

솔브닷 3+ 클래스 단계
https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

❓ 문제

❗ 풀이

• bfs 응용

📗 풀이 코드

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

def bfs(y,x):
    stack = deque([[y,x]])
    while stack :
        y,x = stack.popleft()
        for i in range(4):
            ny,nx = y+dy[i],x+dx[i]
            if 0<=ny<n and 0<=nx<m and maps[ny][nx] and visited[ny][nx]>visited[y][x]+1:
                visited[ny][nx] = visited[y][x]+1
                stack.append([ny,nx])
n,m = map(int,input().split())
maps = []
goal = []
for i in range(n):
    row = list(map(int,input().split()))
    maps.append(row)
    if 2 in row :
        goal += [i,row.index(2)]
visited = [[n*m]*m for _ in range(n)]
visited[goal[0]][goal[1]]=0
dy,dx = [-1,1,0,0],[0,0,-1,1]
bfs(*goal)
for i in range(n):
    row = visited[i]
    for j,num in enumerate(row):
        if num == n*m : # 가지 못한 곳
            row[j] = 0 if not maps[i][j] else -1 # 벽이면 0 아니면 -1   
    print(*row)

📗 코드 해설

• 각 지점에서 목표지점까지의 거리 = 목표지점에서 각 지점까지의 이동거리이므로 출발지를 목표지점으로한
  경로 찾기 BFS 문제이다.
• 각 지점은 maps에 담아두고 최소이동거리를 담아둘 visited를 만든다.
  이때 visited에는 이동거리의 최대치보다 큰 n*m을 담아둔다.
  0으로 담아둔다면 최소이동거리를 구할 때 0이 항상 작으므로 초기화할 때 조건이 여러개 붙어야하기에 이렇게 넣어준다.
• 이후 목표지점의 방문회수는 0으로 초기화해준 뒤 bfs를 진행한다.
• bfs에서 사방을 확인하며 이동가능한 범위인지, 갈 수 있는 땅인지, 이동한다면 최소이동거리인지 확인 후 이동한다.
  이때 이동 전 칸에서 이동거리를 1 늘려주고, 새로운 칸을 stack에 넣어준다.
• bfs 완료 후 한 지점씩 확인하며 이동거리가 0인 곳이 이동할 수 없는 땅인지, 갈 수 있는데 도달하지 못한 위치인지
  확인 후 0과 -1로 변경해준다.