https://www.acmicpc.net/problem/23286
최단거리 탐색 알고리즘으로 접근한 문제다.
풀이
특정 정점에서 다른 정점까지의 최단거리를 계산하는 다익스트라 알고리즘을 사용했다. 이때 핵심은 주어지는 T의 범위가 40,000이라는 점이다. 즉 매 연습마다 40,000번의 그래프 탐색이 일어난다면 시간초과로 이어진다.
정점의 개수 N이 최대 300이며 간선의 최대 개수는 25,000인 점을 고려한다면 이전에 사용했던 정보가 중복으로 요구된다는 합리적인 결론에 도달한다.
따라서 다익스트라 알고리즘을 구현한 뒤 결과 값을 저장할 수 있는 <시작점, 각 정점까지의 최단거리> 형태의 딕셔너리를 생성하여 이전에 요구한 적 없는 시작점이 주어진다면 다익스트라 알고리즘을 통해 해당 결과를 저장한다. 반대로 이전에 요구한 적이 있던 시작점이라면 해당 시작점으로부터의 최단거리 정보는 이미 저장되어 있으므로 바로 출력이 가능하다.
즉 매 횟수마다 최단거리를 계산할 경우 O(4,000 * 25,000)의 시간복잡도로 인해 시간초과가 일어나겠지만, 모든 정점에서 다익스트라 알고리즘을 미리 수행한 결과를 이용한다면 O(300 * 25,000)의 시간복잡도로 시간 단축이 가능하다는 얘기다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
let (N,M,T) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0] | |
var map = Array(repeating: [(node:Int, cost:Int)](), count:N) | |
for _ in 0..<M{ | |
let (u,v,h) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0]-1, $0[1]-1, $0[2])}[0] | |
map[u].append((v,h)) | |
} | |
func dijk(from root:Int) -> [Int]{ | |
var minCost = Array(repeating: -1, count: N) | |
var q = [(node:Int, cost:Int)]() | |
var dq = q | |
minCost[root] = 0 | |
q.append((root,0)) | |
while !q.isEmpty{ | |
dq = q.reversed() | |
q.removeAll() | |
for _ in 0..<dq.count{ | |
let curr = dq.removeLast() | |
if minCost[curr.node] < curr.cost{ continue } | |
for next in map[curr.node]{ | |
let newCost = max(curr.cost, next.cost) | |
if minCost[next.node]<0 || minCost[next.node]>newCost{ | |
minCost[next.node] = newCost | |
q.append((next.node, newCost)) | |
} | |
} | |
} | |
q.sort(by: {$0.cost < $1.cost}) | |
} | |
return minCost | |
} | |
var ans = Dictionary<Int,[Int]>() | |
for _ in 0..<T{ | |
let (S,E) = [readLine()!.split(separator: " ").map{Int($0)!-1}].map{($0[0], $0[1])}[0] | |
if ans[S] == nil{ | |
ans[S] = dijk(from: S) | |
} | |
print(ans[S]![E]) | |
} |
'Problem Solving > BOJ' 카테고리의 다른 글
[17471] 게리멘더링 (0) | 2024.02.06 |
---|---|
[1700] 멀티탭 스케줄링 (0) | 2024.01.30 |
[5582] 공통 부분 문자열 (0) | 2024.01.12 |
[17396] 백도어 (0) | 2023.12.27 |
[23040] 누텔라 트리 (Easy) (0) | 2023.11.10 |