[알고리즘] BOJ 17835 면접보는 승범이네 #Python

김상현·2022년 10월 14일
0

알고리즘

목록 보기
210/301
post-thumbnail

[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)
profile
목적 있는 글쓰기

0개의 댓글