popeye0618

Backend Developer

[python] 백준 - 17270 (연예인은 힘들어)

ko 1 조회수 시리즈 · 알고리즘 #알고리즘

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

골드3 문제이며, 제한 시간은 1초이다.

해결 과정

문제를 처음 봤을 때 다익스트라 알고리즘을 이용해서 푸는 문제인 건 알겠는데 기존 문제들 처럼 start에서 end로의 최단거리를 찾는게 아니라 start와 end에서 각 노드까지의 최단거리를 찾고 그 합이 최소인 노드들을 찾아야 했다.

처음엔 start, end 부터 모든 노드까지 다익스트라를 사용했지만, 너무 비효율적인 것 같아서 생각을 더 해보니 그냥 start, end 를 시작 지점으로 잡고 다익스트라를 두 번 돌면서 visited 리스트를 리턴하면 2번의 다익스트라로 모든 노드의 최단거리를 구할 수 있었다.

그 이후 start -> 특정 노드 + end -> 특정 노드 의 최소를 찾고, 해당하는 노드들 중 (start -> 특정 노드) <= (end -> 특정 노드) 조건을 만족하는 노드를 찾는다. 그리고 나서 번호가 가장 작은 노드를 선택하면 되는 문제였다.

풀이

py
import sys
import heapq
input = sys.stdin.readline

def dijkstra(start):
    hq = []
    heapq.heappush(hq, (0, start))
    visited = [float("inf")] * (v + 1)
    visited[start] = 0

    while hq:
        dist, now = heapq.heappop(hq)

        if dist > visited[now]:
            continue

        for next_node, weight in graph[now]:
            cost = weight + dist
            if visited[next_node] > cost:
                visited[next_node] = cost
                heapq.heappush(hq, (cost, next_node))

    return visited

v, m = map(int, input().split())
graph = [[] for _ in range(v + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

start, end = map(int, input().split())

dist_s = dijkstra(start)
dist_e = dijkstra(end)
min_dist = float('inf')

for i in range(1, v + 1):
    if i == start or i == end:
        continue
    if dist_s[i] == float('inf') or dist_e[i] == float('inf'):
        continue

    min_dist = min(min_dist, dist_s[i] + dist_e[i])

candidate = []
for i in range(1, v + 1):
    if i == start or i == end:
        continue
    if dist_s[i] == float('inf') or dist_e[i] == float('inf'):
        continue

    if dist_s[i] + dist_e[i] == min_dist and dist_s[i] <= dist_e[i]:
        candidate.append(i)

answer = -1
best_s = float('inf')
for node in candidate:
    if dist_s[node] < best_s:
        best_s = dist_s[node]
        answer = node
    elif dist_s[node] == best_s:
        if node < answer:
            answer = node
print(answer)

느낀점

그렇게 어려운 문제는 아니였는데 처음엔 start -> end 의 최단거리가 조건을 만족하는 짧은 거리인 줄 알아서 시간이 조금 걸렸다. 문제를 더 꼼꼼히 읽는 연습이 필요해보인다.

댓글

0

아직 댓글이 없습니다.

댓글 쓰기