https://www.acmicpc.net/problem/2610
유니온 파인드와 플로이드 와샬로 접근 가능한 문제다. 문제 속 함정에 걸려 시간을 많이 소비한 문제다. 문제를 꼼꼼히 읽도록 하자.
풀이
입력받은 간선 정보를 통해 유니온 파인드를 통해 컴포넌트를 구분, 2차원 배열을 통해 각 노드 간의 거리를 갱신한다. 입력이 완료되면 플로이드 와샬 알고리즘을 통해 각 노드 간의 최소거리를 구한다.
유니온 파인드를 통해 알게 된 루트 노드를 입력하면 해당 컴포넌트의 최소 의사전달시간을 구하면 된다. 여기서 주의할 점은 문제에 주어진 "위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록"이라는 부분이다. 해당 부분이 무엇인지 잘 생각하고 접근해야 한다.
다음으로 주의할 점은 "각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다." 부분이다. 처음에 아무 생각 없이 0부터 n까지 순번으로 탐색하면 당연하게 순번대로 출력이 될 거라고 생각했으나, 낮은 순번의 루트를 호출하여 더 높은 번호가 대표가 되는 경우가 존재한다. 결국 대표의 번호를 따로 담아 정렬한 뒤에 출력해주었다.
정답 코드
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 INF = Int.max | |
let n = Int(readLine()!)! | |
let m = Int(readLine()!)! | |
var arr = Array(repeating: -1, count: n) | |
var info = [(a:Int,b:Int)]() | |
var map = Array(repeating: Array(repeating: INF, count: n), count: n) | |
func root(of a:Int)->Int{ | |
if arr[a]<0 { return a } | |
arr[a] = root(of: arr[a]) | |
return arr[a] | |
} | |
func union(a:Int, b:Int){ | |
let rootA = root(of: a) | |
let rootB = root(of: b) | |
if rootA == rootB {return} | |
arr[rootB] = rootA | |
} | |
func dist(from a:Int) -> Int{ | |
var visited = Array(repeating: false, count: n) | |
var q = [a] | |
var idx = 0 | |
var myMin = INF | |
var ans = a | |
visited[a] = true | |
while idx<q.count{ | |
let curr = q[idx] | |
var time = 0 | |
for i in 0..<n{ | |
if map[curr][i]==INF{continue} | |
time = max(time, map[curr][i]) | |
if !visited[i]{ | |
visited[i] = true | |
q.append(i) | |
} | |
} | |
if myMin>time{ | |
myMin = time | |
ans = curr | |
} | |
idx += 1 | |
} | |
return ans+1 | |
} | |
for _ in 0..<m{ | |
let line = readLine()!.split(separator: " ").map{Int($0)!-1} | |
let u = line[0] | |
let v = line[1] | |
union(a: u, b: v) | |
map[u][v] = 1 | |
map[v][u] = 1 | |
} | |
for p in 0..<n{ | |
for i in 0..<n{ | |
for k in 0..<n{ | |
if map[i][p]==INF || map[p][k]==INF || i==k{continue} | |
map[i][k] = min(map[i][k], map[i][p]+map[p][k]) | |
} | |
} | |
} | |
var ans = [Int]() | |
var cnt = 0 | |
for i in 0..<n{ | |
if arr[i] < 0{ | |
cnt += 1 | |
ans.append(dist(from: i)) | |
} | |
} | |
print(cnt) | |
for ans in ans.sorted(by: <){ | |
print(ans) | |
} |
조건에 대한 이해력이 너무나도 중요한 문제였다.
'Problem Solving > BOJ' 카테고리의 다른 글
[2232] 지뢰 (0) | 2022.12.21 |
---|---|
[2143] 두 배열의 합 (0) | 2022.12.20 |
[14594] 동방 프로젝트 (Small) (0) | 2022.12.18 |
[16168] 퍼레이드 (0) | 2022.12.16 |
[13905] 세부 (0) | 2022.12.14 |