[백준 1504번] 파이썬 - 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

 

# 조건

• 방향성 없는 그래프가 주어진다.
• 세준이는 1번에서 N번 정점으로 최단 거리 이동하는데 아래 두 가지 조건 만족해야된다.
  • 임의로 주어진 두 정점은 반드시 통과
  • 한번 이동했던 정점 및 간선도 이동가능하지만 반드시 최단 경로로 이동하여야 한다.
• 이 때, 조건을 만족하는 경로가 없을 경우 -1 출력

 

입력

• 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
• 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000)
• 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
• 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

 

# 접근 방법

• 무방향 그래프에 가중치가 주어져있으므로 다익스트라를 이용해준다.
• '반드시' 지나야 하는 2점이 존재하기에 지나는 점을 기록해주어야 할 필요가 있다.
• bfs를 이용하여 1~N까지의 모든 경로를 탐색해주며 가중치를 더해주고 지나는 점을 함께 기록해준다.
• 이 때 거쳐야 하는 모든 점을 방문했다면 result에 기록해준다.

 

1. bfs 이용 메모리 초과

- 모든 정보를 기록해주니 메모리 초과가 발생하였다.

import sys  
from collections import deque  
sys.stdin = open('input.txt')  
from collections import defaultdict  
  
  
def bfs(num, h, check):  # 시작 정점과 방문한 정점 리스트 받아주기  
    global result, nd1, nd2, graph  
    que = deque()  
    que.append((num,h, check))  
  
    while que:  
        # 방문할 노드와 방문 리스트  
        node, dist, lst = que.popleft()  
  
        # N번 정점에 도착하였다면 조건 체크 해준다.  
        if node == N:  
            # '반드시' 지나야 하는 2정점을 포함하고 있다면  
            # 최단경로 인지 체크            
            if nd1 in lst and nd2 in lst:  
                if dist <= result:  
                    result = dist  
            # 이후 돌아가지 안도록 continue 이용  
            continue  
  
        for i in graph[node]:  
            # 그래프에 연결 간선이 있고 방문하지 않았다면  
            if i[0] not in lst:  
                que.append((i[0], dist+i[1], lst+[i[0]]))  
  
    print(result)  
  
  
  
  
N, E = map(int, input().split())            # 정점의 개수 N, 간선의 개수 E  
graph = [[] for _ in range(N+1)]   # 전체 그래프 연결 관계 기록해줄 리스트  
for _ in range(E):  
  
    a, b, c = map(int, input().split())     # a, b 는 정점, c는 가중치  
    graph[a].append((b,c))  
    graph[b].append((a,c))                         # 양 쪽 정점 모두에게 가중치로  간선 표시해주기  
  
# 필수 방문 노드  
nd1, nd2 = map(int, input().split())  
  
result = 99999999999999  
# 현재 정점과 가중치 방문정점 리스트  
bfs(1, 0, [1])

 

2. BFS 이용 통과 및 heapq 이용 시간 최적화

• 따라서, 1번 정점과 반드시 거쳐야되는 정점에서의 각 정점까지의 거리를 따로 구해준 후
• 최단 거리를 구해주는 방법을 사용하였다.
• 각 최단거리를 구할 때 가지치기를 통해 메모리 및 시간초과를 해결해주었다.

import sys
from collections import deque
input = sys.stdin.readline


def bfs(num, check):  # 시작 정점과 최단거리 리스트 받아주기
    que = deque()
    check[num] = 0
    # 거리와 시작정점 넣어주기
    que.append((0, num))
    while que:
        dist, node = que.popleft()

        if check[node] < dist:
            continue

        for i in graph[node]:
            cost = check[node] + i[1]
            if cost < check[i[0]]:
                check[i[0]] = cost
                que.append((cost, i[0]))

N, E = map(int, input().split())            # 정점의 개수 N, 간선의 개수 E
graph = [[] for _ in range(N+1)]   # 전체 그래프 연결 관계 기록해줄 리스트
for _ in range(E):

    a, b, c = map(int, input().split())     # a, b 는 정점, c는 가중치
    graph[a].append((b,c))
    graph[b].append((a,c))

# 필수 방문 노드
nd1, nd2 = map(int, input().split())
dist_1 = [999999999999999] * (N+1)
dist_nd1 = [999999999999999] * (N+1)
dist_nd2 = [999999999999999] * (N+1)

bfs(1, dist_1)
bfs(nd1, dist_nd1)
bfs(nd2, dist_nd2)

result = min(dist_1[nd1] + dist_nd1[nd2] + dist_nd2[N], dist_1[nd2]+ dist_nd2[nd1] + dist_nd1[N])
print(result if result < 999999999999999 else -1)

• 이 때, 시간을 최적화 하기 위해 heap을 이용하여 비용이 적은 것부터 체크해주도록 하였다.

import sys  
from heapq import heappop, heappush  
input = sys.stdin.readline  
  
  
def bfs(num, check):  # 시작 정점과 최단거리 리스트 받아주기  
    que = []  
    check[num] = 0  
    # 거리와 시작정점 넣어주기  
    heappush(que, (0,num))  
    while que:  
        dist, node = heappop(que)  
  
        if check[node] < dist:  
            continue  
  
        for i in graph[node]:  
            cost = check[node] + i[1]  
            if cost < check[i[0]]:  
                check[i[0]] = cost  
                heappush(que, (cost, i[0]))  
  
N, E = map(int, input().split())            # 정점의 개수 N, 간선의 개수 E  
graph = [[] for _ in range(N+1)]   # 전체 그래프 연결 관계 기록해줄 리스트  
for _ in range(E):  
  
    a, b, c = map(int, input().split())     # a, b 는 정점, c는 가중치  
    graph[a].append((b,c))  
    graph[b].append((a,c))  
  
# 필수 방문 노드  
nd1, nd2 = map(int, input().split())  
dist_1 = [999999999999999] * (N+1)  
dist_nd1 = [999999999999999] * (N+1)  
dist_nd2 = [999999999999999] * (N+1)  
  
bfs(1, dist_1)  
bfs(nd1, dist_nd1)  
bfs(nd2, dist_nd2)  
  
result = min(dist_1[nd1] + dist_nd1[nd2] + dist_nd2[N], dist_1[nd2]+ dist_nd2[nd1] + dist_nd1[N])  
print(result if result < 999999999999999 else -1)

 

위에 맞았습니다 -> deque 이용
아래 맞았습니다 -> heapq 이용

 

확실히 비용이 적은 것 부터 체크해주니 빠른 것이 보인다.