https://www.acmicpc.net/problem/2610

 

2610번: 회의준비

첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이

www.acmicpc.net

유니온 파인드와 플로이드 와샬로 접근 가능한 문제다. 문제 속 함정에 걸려 시간을 많이 소비한 문제다. 문제를 꼼꼼히 읽도록 하자.

 

풀이

입력받은 간선 정보를 통해 유니온 파인드를 통해 컴포넌트를 구분, 2차원 배열을 통해 각 노드 간의 거리를 갱신한다. 입력이 완료되면 플로이드 와샬 알고리즘을 통해 각 노드 간의 최소거리를 구한다. 

 

유니온 파인드를 통해 알게 된 루트 노드를 입력하면 해당 컴포넌트의 최소 의사전달시간을 구하면 된다. 여기서 주의할 점은 문제에 주어진 "위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록"이라는 부분이다. 해당 부분이 무엇인지 잘 생각하고 접근해야 한다.

 

다음으로 주의할 점은 "각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다." 부분이다. 처음에 아무 생각 없이 0부터 n까지 순번으로 탐색하면 당연하게 순번대로 출력이 될 거라고 생각했으나, 낮은 순번의 루트를 호출하여 더 높은 번호가 대표가 되는 경우가 존재한다. 결국 대표의 번호를 따로 담아 정렬한 뒤에 출력해주었다.

 

정답 코드

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)
}
view raw 2610.swift hosted with ❤ by GitHub

조건에 대한 이해력이 너무나도 중요한 문제였다.

'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

+ Recent posts