[백준 17835] 면접보는 승범이네

카테고리 없음

[백준 17835] 면접보는 승범이네

뚱졍뚱졍 2024. 4. 8. 23:34

문제

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.

면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.

모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.

속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.

승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.

입력

첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다.

다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다.

마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.

출력

첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.

둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.

풀이

처음 생각한 방법은 N개의 도시를 기점으로 최단거리 맵들을 형성하고 면접장까지의 최단거리가 가장 먼 도시를 찾아내는 것이었지만 도시 개수의 범위만 보아도 시간초과가 뻔하기에 구현하진 않았다

어떤 방법으로 시간을 줄일까 고민해본 결과 면접장들의 위치를 기점으로 각 도시들까지의 최단거리를 구해보려했지만 단방향 도로 설계를 고려하지 못하여 테스트케이스가 틀렸다

이후 우선순위 큐의 특징을 생각하여 각 도시의 최단거리 맵을 형성하는 과정에서 면접장을 만나면 바로 종료하여 시간을 줄여보려했지만 일차적으로 시간초과가 발생했고 다시 생각해봤을 때 가장 먼저 만난 면접장까지의 거리가 최단거리라는 보장도 없다

INF = int(1e11)

N,M,K = map(int,input().split())
R = [[] for _ in range(N+1)]
for _ in range(M):
    U,V,C = map(int,input().split())
    R[V].append((C,U))
interview = list(map(int,input().split()))
distance = [INF for _ in range(N+1)]
res = (0,0)

# 우선순위 큐 다익스트라
def dijkstra(start):
    distance[start] = 0
    Q = []
    heappush(Q,(0,i))

    while Q:
        nowCost, nowNode = heappop(Q)
        if distance[nowNode] < nowCost:
            continue
        for nextCost, nextNode in R[nowNode]:
            cost = nowCost+nextCost
            if cost < distance[nextNode]:
                distance[nextNode] = cost
                heappush(Q,(cost,nextNode))

for i in interview: # 각 면접장들의 위치를 0으로 하여 최단거리 맵 업데이트
    dijkstra(i)  

distance[0] = -1    # 0번 노드 inf 초기화

d = max(distance)
c = distance.index(d)
print(c)
print(d)

입력받는 단방향 도로를 역방향으로 저장하고 면접장들의 위치들을 모두 거리 0으로 설정하여 다른 도시들까지의 최단거리를 업데이트하였다

풀이 힌트를 얻어서 진행하였고 최단거리 맵을 우선순위 큐로 형성할 때 0이 되는 출발점을 여러개 넣어서 만들수도 있다는 사실을 알수있었다

참고로 INF = int(1e9) 을 하였다가 오답이 떠서 당황했다

입력값의 범위를 잘 확인하자..