백준 4485번: 녹색 옷 입은 애가 젤다지? 파이썬 코드(다익스트라)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

import sys
import heapq

INF = sys.maxsize

x = [0,0,-1,1]
y = [-1,1,0,0]
count = 0

while 1:
    n = int(sys.stdin.readline())
    count += 1
    visited = [[0 for _ in range(n)]for _ in range(n)]
    if n == 0:
        break
    graph = []
    dist = [[INF for _ in range(n)] for _ in range(n)]
    for i in range(n):
        temp = list(map(int, sys.stdin.readline().split()))
        graph.append(temp)
    heap = []
    heapq.heappush(heap, [graph[0][0],[0,0]])
    while heap:
        cost, now = heapq.heappop(heap)
        visited[now[0]][now[1]] = 1
        if dist[now[0]][now[1]] > cost:
            dist[now[0]][now[1]] = cost
            if now[0] == n - 1 and now[1] == n - 1:
                break
        else:
            continue
        for i in range(4):
            if 0<=now[0]+x[i]<n and 0<=now[1]+y[i]<n and visited[now[0]+x[i]][now[1]+y[i]] == 0:
                if dist[now[0]+x[i]][now[1]+y[i]] > cost + graph[now[0]+x[i]][now[1]+y[i]]:
                    heapq.heappush(heap, [cost+graph[now[0]+x[i]][now[1]+y[i]], [now[0]+x[i],now[1]+y[i]]])
    print("Problem {}: {}".format(count, dist[n-1][n-1]))

설명

x,y 리스트를 만들어 좌우앞뒤를 검사해주면 평범하게 풀 수 있는 다익스트라 문제이다. 메모리 제한이 널널해서 굳이 visited에 cost를 넣어주며 할 필요는 없었다.

문제점

내가 자주하는 실수 중 하나인데, visited에 값을 직접 넣어서, if [now[0]+x[i],now[1]+y[i]] not in visited: 이런 식으로 검사를 해서 시간초과를 내곤 하는데 visited = [[0 for _ in range(n)]for _ in range(n)]로 해주니 잘 된다.