[BOJ] [Python] 18352번 : 특정 거리의 도시 찾기

다익스트라 알고리즘을 이용하여 풀었다.

 

처음에는 시간 초과가 났다. 통과하기 위한 과정을 아래에 적어놓았다.

 

 

 

아래는 통과한 코드이다.

 

import sys
import heapq

input = sys.stdin.readline

n, m, k, x = map(int, input().split())

route = []

val = [10000000] * (n+1)
val[x] = 0

for n_c in range(n+1):
    route.append([])

for m_c in range(m):
    num = list(map(int, input().split()))
    route[num[0]].append(num[1])

order = []  # 순서 리스트

heapq.heappush(order, (0, x)) # (거리, 위치)

while (order):

    dist, now = heapq.heappop(order)

    for i in route[now]:
        cal = dist + 1

        if cal < val[i]:
            val[i] = cal
            heapq.heappush(order, (cal, i))

result = []

for v in range(len(val)):
    if val[v] == k:
        result.append(v)

if (len(result) == 0):
    print(-1)
else:
    result.sort()
    for r in result:
        print(r)

 

 

 

 

통과한 코드로 고치기까지[시간 초과 문제 해결]의 과정이다. 

 

1. 간선의 최대 입력 줄은 1,000,000이다.

input으로 입력을 받게 되면 시간 초과가 발생한다. 그러므로 sys함수를 사용해서, readline으로 입력을 받는다.

 

2. dict을 사용하는 이유 중 하나는 시간 절약인데, for문으로 돌려버리면 시간 복잡도가 O(n)가 된다.

dict을 사용해야 하는 이유가 사라진다. list로 바꾼다.

 

3. heapq를 사용해서, push pop을 하였다. 하지만 list를 사용해서 push pop을 해도 무방하다.

 

4. check 리스트를 삭제했다.

한번 방문했던 곳을 기준으로는, 현 위치 + 가중치 값과 도착지와의 관계를 보지 않으려했다.

아래처럼 조건문 아래에서 다음 가야할 위치를 추가하게 되면, check 리스트 없이 수행이 가능하다.

 

 

        if cal < val[i]:
            val[i] = cal
            heapq.heappush(order, (cal, i))

 

 

 

 

아래는 시간 초과한 코드이다.

 

# 도시 개수 : N개 (1번 ~ N번)
# 단반향 수 [도로의 개수] : M개
# 찾는 최단 거리 [거리 정보] : K
# 시작 도시 [출발 도시] : X번

# 무한대를 나올 수 없는 값으로 표기
# 최단 거리 미존재 -> -1 출력

# 1- > 2
# 1 -> 3

# 2 -> 3
# 2 -> 4

# 경로 : {1 : 2, 1: 3, 2 : 3, 2: 4}
# 값 : [x, 0, 무한, 무한, 무한]

num = list(map(int, input().split()))

n = num[0]
m = num[1]
k = num[2]
x = num[3]

route = {}

for n_c in range(1, n+1):
    route[n_c] = []

for m_c in range(m):
    num = list(map(int, input().split()))
    route[num[0]].append(num[1])

val = [10000000] * (n+1)
val[x] = 0

check = [x] # 중복 제거 리스트
order = [x] # 순서 리스트

# print("rou", route)
# print("val", val)

while(order):

    # print("che", check)
    # print("ord", order)

    for i in route[order[0]]:
        if i not in check:
            check.append(i)
            order.append(i)

        cal = val[order[0]] + 1

        if cal < val[i]:
            val[i] = cal

    order = order[1:]

# print("rou", route)
# print("val", val)

result = []
for v in range(len(val)):
    if val[v] == k:
       result.append(v)

if(len(result) == 0):
    print(-1)
else:
    result.sort()
    for r in result:
        print(r)