문제
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
입력 예시 1
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3출력 예시 1
10문제 이해
N개의 노드(마을)이 있다. 1번 부터 N개의 노드에 사람이 한명씩 산다. X노드에서 파티를 할 예정이고, 사람들은 각 노드에서 출발해서 X에서 파티를 하고 다시 자신의 노드로 돌아간다. 모든 사람들이 최단거리로 X에 갔다가 자신의 노드로 돌아올 것이다. 이번 문제는 이중에서 가장 최단거리로 가도 먼 거리가 얼마인지 출력하는 것이다.
이 문제는 두 가지 풀이로 문제를 해결할 수 있다.
첫번째 방법
첫번째 방법은 1번부터 X번까지 가는 최단거리를 각각 다익스트라를 돌려서 값을 구하고, X를 시작점으로 다익스트라를 돌려서 두 값을 합쳐서 그중에서 가장 큰 값을 구하는 방법이다. 그렇게 하려면 1번부터 N번노드까지 총 N번 다익스트라를 돌리고, X에서 나머지 노드로 가는 다익스트라를 1번 돌려야 한다. 그러면 총 N+1번의 다익스트라를 수행한다.
노드와 간선 조건:
N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000)
다익스트라 알고리즘은 간선의 개수 M, 노드의 갯수 N일 때 "M*logN"의 시간 복잡도를 가진다.
첫번째 방법 시간복잡도
(N+1) M logN
= 1,000 10,000 log 1,000 (2*10정도)
= 1,000 10,000 * 10
= 1억 정도
문제의 제한시간은 1초이고, 보통 1초에 1억번 정도의 연산을 한다. 그래서 제출하기애매한 시간 복잡도이다. 그래도 코딩테스트 상황이 아니라면 연습도 하고 구현력도 키울겸 시도해보기엔 좋다. 실제로 구현해서 제출하니 생각보다 시간이 적게 걸린다. 0.5초도 안걸린다. 정답판정도 받았다.
첫 번째 풀이
# 백준 1238번 풀이 1
# 풀이가 두 가지 방법이 가능해서 2가지로 소스파일을 따로 만든다.
# 1번부터 N번까지 다익스트라 + x에서 각 번호 까지 다익스트라
# 총 N+1번 다익스트라를 돌리는 풀이이
# 읽는 속도 효율화
import sys
input = sys.stdin.readline
# Import PriorityQueue
from queue import PriorityQueue
def Dijkstra(start_node):
global distance_list
distance = [INF] * (N+1)
pq = PriorityQueue()
pq.put([0, start_node])
distance[start_node] = 0
while not pq.empty():
cur_distance, cur_node = pq.get()
for adj_node, adj_distance in adj_list[cur_node]:
temp_distance = cur_distance + adj_distance
if temp_distance < distance[adj_node]:
distance[adj_node] = temp_distance
pq.put([temp_distance, adj_node])
return distance
# 0. 입력 및 초기화
INF = int(1e12)
N, M, X = map(int, input().split())
# N: 마을(노드)의 수
# M: 단방향 간선의 갯수
# X: 파티를 여는 마을(노드)
adj_list = [[] for _ in range(N+1)]
distance_to_X = [] # Dijkstra from i to X
distance_X = [] # Dijkstra to Everynode
# Create adj_list
for _ in range(M):
a, b, c = map(int, input().split())
adj_list[a].append([b, c])
# Dijkstra from i to X
for i in range(1, N+1):
distance = Dijkstra(i)
distance_to_X.append(distance[X])
# Dijkstra from X to Everynode
distance_X = Dijkstra(X)
result = []
for i in range(1, N+1):
result.append(distance_to_X[i - 1] + distance_X[i])
max_value = max(result)
print(max_value)두 번째 방법
1번부터 N번까지의 노드에서 X노드로 가는 것을 N번의 다익스트라를 통해 구했지만, 이걸 한번의 다익스트라로 해결할 수 있다. 그래프 자체를 완전히 뒤집으면 된다. 간선의 방향을 반대로 설정하면, X번에서 모든 노드로 가는 값을 구하면 원래 그래프에서 모든 노드에서 X로 가는 값과 같다. 즉, 그래프를 뒤집어서 도착점을 기준으로 다익스트라를 돌릴 수도 있다는 말이다.
시간복잡도
2 M logN
= 2 10,000 log 1,000 (2*10정도)
= 2 10,000 * 10
= 200,000 (20만 정도)
확실히 안정적으로 정답판정을 받을 수 있다.
두 번째 풀이
# 백준 1238번 파티 풀이 2
# 1번부터 N번까지에서 X로 가는 다익스트라를 N번이나 하기 부담스럽다면
# graph를 완전히 뒤집어서 X에서 시작하는 다익스트라를 돌리면 한번에 해결할 수 있다.
# 읽는 속도 효율화
import sys
input = sys.stdin.readline
# Import PriorityQueue
from queue import PriorityQueue
# Dijkstra Algorithm
def Dijkstra(start_node, list):
distance = [INF] * (N+1)
pq = PriorityQueue()
pq.put([0, start_node]) # cur_distance, cur_node
distance[start_node] = 0
while not pq.empty():
cur_distance, cur_node = pq.get()
for adj_node, adj_distance in list[cur_node]:
# 다음 노드까지의 거리를 합친 값
temp_distance = cur_distance + adj_distance
if temp_distance < distance[adj_node]:
distance[adj_node] = temp_distance
pq.put([temp_distance, adj_node])
return distance
# 0. 입력 및 초기화
INF = int(1e12)
N, M, X = map(int, input().split())
# N: 마을(노드)의 수
# M: 단방향 간선의 갯수
# X: 파티를 여는 마을(노드)
# 1. Create adj_list & reverse adj_list
adj_list = [ [] for _ in range(N+1)]
adj_list_reverse = [ [] for _ in range(N+1)]
for _ in range(M):
a, b, c = map(int, input().split())
adj_list[a].append([b, c])
adj_list_reverse[b].append([a, c])
# 2. Excute Dijkstra Algorithm
distance_to_X = Dijkstra(X, adj_list_reverse)
distance_to_everynode = Dijkstra(X, adj_list)
# 3. Print result
result = []
for i in range(1, N+1):
result.append(distance_to_X[i] + distance_to_everynode[i])
max_value = max(result)
print(max_value)
아래가 1번 풀이, 위가 2번 풀이이다.
