쉬운 최단거리

https://www.acmicpc.net/problem/14940

 

나의 풀이

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

n, m = map(int, input().rstrip().split())
queue = deque()
start_pt = ()
new_map = []
for i in range(n):
    now_list = list(map(int, input().rstrip().split()))
    if (not start_pt) and (2 in now_list):
        start_pt = (i, now_list.index(2))
        queue.append(start_pt)
    new_map.append(now_list)
new_map[start_pt[0]][start_pt[1]] = 0

# BFS 탐색
while queue:
    a,b = queue.popleft()
    for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
        new_a, new_b = a+m_a, b+m_b
        if (0 <= new_a < n) and (0 <= new_b < m) and (new_map[new_a][new_b] == 1):
            new_map[new_a][new_b] = new_map[a][b] + 1
            queue.append((new_a, new_b))

# 방문 가능 인접 경로 1 치환
for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
    new_a, new_b = start_pt[0] + m_a, start_pt[1] + m_b
    if (0 <= new_a < n) and (0 <= new_b < m) and (new_map[new_a][new_b] != 0):
        new_map[new_a][new_b] = 1

# 방문 못 하는 경로 -1 치환
for i in range(n):
    for j in range(m):
        if ((i,j) not in ((start_pt[0]+1, start_pt[1]),(start_pt[0]-1, start_pt[1]),(start_pt[0], start_pt[1]+1),(start_pt[0], start_pt[1]-1))) and (new_map[i][j] == 1):
            new_map[i][j] = -1

# 최종 출력
for i in new_map:
    i = list(map(str, i))
    print(' '.join(i))

 

시간 복잡도

# BFS 탐색
while queue : BFS 모든 경로를 탐색하므로 ( 이차형 시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 이차형 시간 복잡도 ( O(n**2) )