[최단 경로] 백준 4485번: 녹색 옷 입은 애가 젤다지? / 골드 4

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

4485번: 녹색 옷 입은 애가 젤다지?

import sys
import heapq

def dijkstra():
    global answer
    q = []
    heapq.heappush(q, [graph[0][0], 0, 0]) # cost, x, y
    while q:
        cost, x, y = heapq.heappop(q)
        if n*x+y not in visited:
            visited[n*x+y] = cost
            if x == n-1 and y == n-1: # finish
                answer = cost
                break
            for j in range(4):
                nx = x + dx[j]
                ny = y + dy[j]
                if 0 <= nx < n and 0 <= ny < n and n*nx+ny not in visited:
                    heapq.heappush(q, [cost + graph[nx][ny],nx,ny])

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

result = []
while True:
    n = int(input())
    if n == 0:
        break

    graph = []
    visited = {}
    for i in range(n):
        graph.append(list(map(int, input().split())))

    global answer
    answer = sys.maxsize
    dijkstra()
    result.append(answer)

for i in range(len(result)):
    print("Problem {0}: {1}".format(i+1, result[i]))

처음에 dfs로 접근했다가 시간 초과가 발생했다.
왜 다익스트라로 접근해야 하는가?

모든 노드를 탐색하긴 하되 각 노드까지의 최단 거리는 정해져있다.

그래서 dfs로 하면 이미 최단 거리를 알아낸 노드까지도 계속 지나치기 때문에
시간이 굉장히 오래걸리게 된다.

 

++ 계속 실패한 이유는 마지막 출력에 있었다.

위에 처럼 안하고

print('Problem', i+1, ':', result[i])로 하면 틀린다... 번호와 땡땡 사이에 띄어쓰기가 생기기 때문에..

저 방식을 필수로 알아놔야 겠다.

 

배운점

- .format()을 이용하여 콤마 사이를 띄어쓰기 없이 출력할 수 있다.