특정한 최단 경로

#BOJ1504

그래프이론

매일 골드 이상 문제 푸는 걸 틈틈이 해보고 있는데 내가 잘 못하는 영역인 그래프이론 부분의 문항을 풀기 위해서 만든 문제집 문제 중 하나를 선정해서 풀기 시작했다. 다익스트라 하면 사실 어느정도 풀이 방향이 고정되어 있고 그 안에서 한 두개의 변수 변환 만으로도 풀 수 있을 것이라고 생각하였다. 우선 제약 조건들을 고려하지 않고 그냥 다익스트라로 짜면 어떤 식으로 나올지만 생각하면서 문제를 풀었다. 다익스트라로만 구현하면 아래와 같이 나오지만 당연히 제약조건이 있기 때문에 이제부터 진짜 문제풀이 시작이라고 볼 수 있다. 사실 이정도라면 원래는 실버1 정도였을 것 같다.

import sys

N, E = map(int, sys.stdin.readline().split())
arr = [[]for _ in range(N + 1)]

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a].append([b, c])
    arr[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().split())

visited = [float("inf")] * (N + 1)
visited[1] = 0
q = [[1, 0]]
while q:
    s, v = q.pop()
    if visited[s] < v:
        continue
    for e, w in arr[s]:
        if visited[e] > v + w:
            visited[e] = v + w
            q.append([e, v + w])
print(visited[-1])

뭐 이거야 간단한 다익스트라이니 누구나(다익스트라를 공부한) 구현할 수 있는 수준일텐데 여기서 어떻게 해야할까를 고민하면서 flag를 세워볼까 하였다. 근데 그러면 논리가 너무 내 나쁜 머리로 설계하기에 까다로울 것 같아서 그냥 깔끔하게 레이어를 쌓기로 하였다. 뭔소리냐면 다익스트라를 그냥 개많이 하는거다. v1, v2가 아니라 v1만 주어진다고 가정하자. 그러면 아래 코드는 정해를 던질 것이다.

import sys

N, E = map(int, sys.stdin.readline().split())
arr = [[]for _ in range(N + 1)]

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a].append([b, c])
    arr[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().split())

visited = [float("inf")] * (N + 1)
visited[1] = 0
q = [[1, 0]]
while q:
    s, v = q.pop()
    if visited[s] < v:
        continue
    for e, w in arr[s]:
        if visited[e] > v + w:
            visited[e] = v + w
            q.append([e, v + w])
#아래부터 그냥 v1시작으로 한 바퀴를 더 돈다고 생각하면 편하다.
q = [[v1, visited[v1]]]
visited = [float("inf")] * (N + 1)
while q:
    s, v = q.pop()
    if visited[s] < v:
        continue
    for e, w in arr[s]:
        if visited[e] > v + w:
            visited[e] = v + w
            q.append([e, v + w])
print(visited[-1])

이렇게 하면 시간 초과가 좀 걱정되긴 하지만 우선 구현해 보았다.

import sys

# N: 정점의 개수, E: 간선의 개수 입력받기
N, E = map(int, sys.stdin.readline().split())
# 인접 리스트를 사용하여 그래프 구현
arr = [[]for _ in range(N + 1)]

# 간선 정보 입력받기
for _ in range(E):
   a, b, c = map(int, sys.stdin.readline().split())
   arr[a].append([b, c])
   arr[b].append([a, c])

# 반드시 거쳐야 하는 정점 v1, v2 입력받기
v1, v2 = map(int, sys.stdin.readline().split())

# 1번 정점에서 각 정점까지의 최단 거리 계산 (다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[1] = 0
q = [[1, 0]]
while q:
   s, v = q.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           q.append([e, v + w])

# v2에서 v1까지의 최단 거리 계산 (역방향 다익스트라 알고리즘)
qq = [[v2,visited[v2]]]
q = [[v1, visited[v1]]]

visited = [float("inf")] * (N + 1)
visited[v1] = q[0][1]
while q:
   s, v = q.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           q.append([e, v + w])
q = [[v2, visited[v2]]]

# v1에서 N번 정점까지의 최단 거리 계산 (다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[v2] = q[0][1]
while q:
   s, v = q.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           q.append([e, v + w])
ans = visited[-1]

# v2에서 1번 정점까지의 최단 거리 계산 (역방향 다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[v2] = qq[0][1]
while qq:
   s, v = qq.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           qq.append([e, v + w])
qq = [[v1, visited[v1]]]

# 1번 정점에서 v1까지의 최단 거리 계산 (다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[v1] = qq[0][1]
while qq:
   s, v = qq.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           qq.append([e, v + w])
ans = min(visited[-1], ans)

# 결과 출력
if ans == float("inf"):
   print(-1)
else:
   print(ans)

되네? 역시 나야 ㅋㅋ