쉬운 최단거리(백준 14940번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상✓

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

나의 풀이

import sys
from collections import deque

def BFS(my_map,x,y,visited,n,m):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    visited[x][y]=True
    my_map[x][y]=0
    queue=deque()
    queue.append((x,y))
    while queue:
        v=queue.popleft()
        for i in range(4):
            mx=v[0]+dx[i]
            my=v[1]+dy[i]
            if 0<=mx<n and 0<=my<m and not visited[mx][my] and my_map[mx][my]:
                visited[mx][my]=True
                queue.append((mx,my))
                my_map[mx][my]=my_map[v[0]][v[1]]+1
    return my_map

input=sys.stdin.readline
n,m=map(int,input().strip().split())
my_map=[]
visited=[[False]*m for _ in range(n)]
for n_i in range(n):
    l=list(map(int,input().strip().split()))
    my_map.append(l)
x=0
y=0
for i in range(n):
    stop=0
    for j in range(m):
        if my_map[i][j]==2:
            x=i
            y=j
            stop=1
            break
    if stop==1:
        break
my_map=BFS(my_map,x,y,visited,n,m)
for i in range(n):
    for j in range(m):
        if my_map[i][j]==1 and not visited[i][j]:
            print(-1,end=' ')
        else:
            print(my_map[i][j],end=' ')
    print('')

• BFS를 사용하여 문제를 풀었다.
• my_map에서 기준점인 2의 위치를 찾고, 2의 위치를 기준으로 얼마의 거리가 떨어져 있는지, my_map에 저장하는 형태로 하였다.
• 위 작업을 끝낸 후, my_map에서 1의 값을 갖는데, 방문하지 않는 지점은 도달할 수 없는 지점이기 때문에 -1을 출력하도록 하였다.