[BOJ] 17835 면접보는 승법이네 바로가기
📍 문제
마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 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개가 공백을 두고 주어진다.
📍 출력
첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.
둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.
📍 풀이
💡 고찰
- 그래프에서 1개의 노드를 기준으로 다른 노드까지 가는 최단 거리를 구하는 방법인 다익스트라(
Dijkstra) 알고리즘 을 이용하였다. - 처음에는 면접장이 존재하는 노드를 제외한 모든 노드에서 면접장이 존재하는 노드에 도착하는 최단 거리를 힙(
heap) 자료구조를 이용하여 답을 구하였지만, 시간 초과 문제가 발생했다. - 시간 초과 문제를 해결하기 위해 면접장이 존재하는 모든 노드를 시작점으로 단 한번 다익스트라를 적용하여 면접장 기준 최장 거리에 존재하는 도시의 번호와 거리를 구할 수 있었다.
📌 문제 풀이
✏️ 1. 주어진 방향 그래프를 역뱡향 그래프로 생성한다.
for _ in range(M):
U, V, C = map(int,stdin.readline().split())
graph[V].append((U,C)) # 주어진 방향의 역뱡향으로 그래프 생성- 역방향 그래프로 생성한 이유는 면접장이 존재하는 도시를 기준으로 나머지 도시들의 최단 거리를 구하기 위함이다.
✏️ 2. 다익스트라를 적용하기 위한 데이터 구조를 생성한다.
distance = [maxsize] * (N+1)
queue = deque(starts)distance는 면접장 기준에서의 최단 거리 정보를 담은 리스트이다.queue는 면접장이 존재하는 노드의 위치를 초기화할 덱 자료구조이다.
✏️ 3. 면접장이 존재하는 노드 기준 현재 노드까지의 최단 거리 갱신
while queue:
currentNode = queue.popleft()
for nextNode, weight in graph[currentNode]:
if distance[nextNode] > distance[currentNode] + weight:
distance[nextNode] = distance[currentNode] + weight
queue.append(nextNode)- 현재까지 이동거리(
distance[currentNode]) + 현재 노드에서 다음 노드까지의 거리(weight)가 다음 노드의 이동 거리(distance[nextNode])보다 작다면 최단거리를 갱신해준다.
✏️ 4. 면접장에서 최장 거리의 도시 탐색
for i in range(1,N+1):
if distance[i] != maxsize and distance[i] > dist:
city, dist = i, distance[i]✍ 코드
# 17835 면접보는 승범이네 < 골드 2 >
from sys import maxsize, stdin, maxsize
from collections import defaultdict, deque
def solution(N, graph, starts):
city, dist = 0, 0
distance = [maxsize] * (N+1) # 면접장 기준에서의 최단 거리 정보를 담은 리스트
queue = deque(starts) # 면접장 위치 정보
# 면접장 거리값 0으로 초기화
for start in starts:
distance[start] = 0
# 면접장 기준 각 도시 별 최단 거리 구하기
while queue:
currentNode = queue.popleft()
# 현재 도시와 연결된 모든 도시와 도시 간의 거리 탐색
for nextNode, weight in graph[currentNode]:
# 최소 거리값 갱신
if distance[nextNode] > distance[currentNode] + weight:
distance[nextNode] = distance[currentNode] + weight
queue.append(nextNode)
# 최장거리 도시 위치 탐색
for i in range(1,N+1):
if distance[i] != maxsize and distance[i] > dist:
city, dist = i, distance[i]
return city, dist
# 입력
graph = defaultdict(list)
N, M, K = map(int,stdin.readline().split())
for _ in range(M):
U, V, C = map(int,stdin.readline().split())
graph[V].append((U,C)) # 주어진 방향의 역뱡향으로 그래프 생성
starts = list(map(int,stdin.readline().split()))
# solution()
city, dist = solution(N, graph, starts)
# 결과
print(city)
print(dist)