[python] 백준 18352 특정 거리의 도시 찾기 - 메모리 초과 해결

문제

 

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

 

 

풀이

 

풀이 ( 172212 KB, 2904 ms)

 

import sys, heapq
input = sys.stdin.readline

def djk(start) :
    global dist, cities

    heap = []
    heapq.heappush(heap, (0, start))
    dist[start] = 0

    while heap :
        curd, cur = heapq.heappop(heap)
        if dist[cur] < curd : continue # 지금이 더 작으면 갱신 안함 (== 이미 방문 한 것)

        for i in cities[cur] :
            cost = curd + i[1]
            if dist[i[0]] > cost :
                dist[i[0]] = cost
                heapq.heappush(heap, (cost, i[0]))

n, m, k, x = map(int, input().split()) # 도시 n개(1 ~ n), 도로 m개, 거리 k, 출발도시 x

cities = [[] for _ in range(n + 1)]
for _ in range(m) :
    r, c = map(int, input().split())
    cities[r].append((c, 1))

dist = [300001] * (n + 1)

djk(x)

ans = []
for i in range(1, n + 1) :
    if dist[i] == k :
        ans.append(i)

if len(ans) == 0 :
    print(-1)
else :
    for i in ans : print(i)

 

배운 점

 

시간 초과 해결 방법

 

1. 도시 정보를 2차원 리스트가 아닌 1차원 리스트로 입력 받음 : 출발 노드를 인덱스로 이용하여 해당 인덱스 번호에 튜플로 도착 노드 인덱스와 가중치를 입력

2. 도시 정보는 초기에 0이 입력된 리스트가 아닌 빈 리스트로 이루어진 리스트로 초기화