[백준 1504번][Python] - 특정한 최단 경로

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

 

 

 

 

 

 

 

# BFS풀이과정

1. 문제의 조건을 만족시키면서 목적지에 도달하는 경우는 총 4가지이다.

• 1번 → a번 + a번 → b번 + b번 → N번
• 1번 → b번 + b번 → a번 + a번 → N번
• 1번 → b번 + b번 → a번 + a번 → b번 + b번 → N번
• 1번 → a번 + a번 → b번 + b번 → a번 + a번 → N번

2. 위 4가지 경우 중에서 가장 작은 값을 찾으면 된다.

3. BFS를 이용해서 각 노드 간 최소 비용을 구한다

4. 구한 비용을 바탕으로 (1)의 4가지 경우를 비교

5. 가장 작은 값을 출력

6. 이동이 불가능할경우 대비해서 예외처리로 -1을 출력

 

※ 3,4번의 경우도 고려해야하는 이유? ※

• b → N, 1 → b의 경로만 비용이 100, 나머지 경로는 비용이 1밖에 되지 않는다고 고려해 보자.
• 그렇게 되면 (1)의 4번째 경로가 가장 비용이 적은 상황이 발생한다.

 

[BFS를 이용한 코드 - 메모리초과]

# ex_1504
import sys
from collections import deque
N,E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

# 거리계산함수
def cal(start,end):
    minCost = 1e8
    q = deque([([start],start,0)])
    while q:
        (v,start,cost) = q.popleft()
        if start == end:
            minCost = min(minCost,cost)
        for x,c in graph[start]:
            if x not in v:
                q.append((v+[x],x,cost+c))
    return(minCost)

# 간선은 양방향임
for _ in range(E):
    s,e,cost = map(int, sys.stdin.readline().split())
    graph[s].append((e,cost))
    graph[e].append((s,cost))

# 경유지 a,b
a,b = map(int, sys.stdin.readline().split())

# 필요한 거리 계산
aTOb = cal(a,b)
sTOa = cal(1,a)
sTob = cal(1,b)
aTOn = cal(a,N)
bTOn = cal(b,N)

# 최단경로 계산
try:
    print(min(sTOa+aTOb+bTOn, sTob+aTOb+aTOn, sTob+aTOb+aTOb+bTOn, sTOa+aTOb+aTOb+aTOn))
except(Exception):
    print(-1)

 

BFS를 사용한 코드는 메모리 초과가 발생하였다.

아무래도 큐에 너무 많은 요소를 집어넣어서 큐가 너무 많은 메모리를 차지하기 때문으로 보인다.

그래서 최소힙을 사용한 다익스트라 알고리즘을 사용하여 풀어보았다.

 

 

[다익스트라 알고리즘을 이용한 코드 - 통과]

# ex_1504
import sys
import heapq
N,E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

# 간선은 양방향임
for _ in range(E):
    s,e,cost = map(int, sys.stdin.readline().split())
    graph[s].append((e,cost))
    graph[e].append((s,cost))

# 경유지 a,b
a,b = map(int, sys.stdin.readline().split())

# 거리계산함수
def dijkstra(start,end):
    distance = [1e8 for _ in range(N+1)]    # 기준 노드로부터 인덱스(=X번 노드) 까지의 거리를 나타내는 배열
    heap = []
    heapq.heappush(heap, (0,start))
    distance[start] = 0
    while heap:
        d,s = heapq.heappop(heap)
        if distance[s] < d:
            continue
        for tup in graph[s]:
            cost = d + tup[1]   # 도착 노드별 누적 비용
            if cost < distance[tup[0]]:
                distance[tup[0]] = cost
                heapq.heappush(heap,(cost,tup[0]))

    return(distance[end])

# 필요한 거리 계산
aTOb = dijkstra(a,b)
sTOa = dijkstra(1,a)
sTob = dijkstra(1,b)
aTOn = dijkstra(a,N)
bTOn = dijkstra(b,N)

# 최종적으로 최단경로 계산
result = min(sTOa+aTOb+bTOn, sTob+aTOb+aTOn, sTob+aTOb+aTOb+bTOn, sTOa+aTOb+aTOb+aTOn)
if result >= 1e8:
    print(-1)
else:
    print(result)

 

문제없이 통과하였다. 기존 BFS코드의 경우, 간선이 많이 주어지면 생각보다 큐에

많은 데이터가 들어가는 상황이 생기는 것을 생각하지 못했던 것이 원인인 것 같다.

메모리도 조금 더 신경 쓸 필요가 있을 것 같다.