백준 - 회의준비 - 2610 - swift

 

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

2610번: 회의준비

 

 

유형은 bfs탐색 또는 플로이드 워셜로 볼 수 있다. 

 

문제를 푸는 데 있어서 핵심 로직은 다음과 같다.

1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다.
2. 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다.

사실 1번을 만족한다면 2번은 자동적으로 만족할 수밖에 없다.

즉 2번은 그다지 고려하지 않아도 되는 부분이다.

 

그러므로, 위원회를 만들어주기 위한 그룹핑이 필요하다. 

이는 간단하게 bfs또는 dfs를 이용하여 그룹을 지어준다. 

 

다음은 각 의원회안에서 의사전달시간 중 최댓값이 최솟값으로 만들어야 한다.

이는 각 그룹안에 속하는 인원들을 모두 bfs탐색 또는 플로이드 워셜을 이용하여 모든 인원들의 거리를 계산한다.

그래서 그안에서 가장 최솟값이 되는 인원을 대표로 선정한다. 

 

모든 bfs탐색 또는 플로이드워셜이 가능한 이유도 미리 알아야 한다.

인원은 총 최대 100명이므로, 플로이드워셜 알고리즘은 O(N^3) 이므로 충분하고, 

모든 bfs탐색은 100명에서 최대 관계수는 100*99/2 = 4950으로, 

100*4950 = 50만이므로, 충분하다. 

 

bfs 탐색만 사용 

let N = Int(readLine()!)!
let M = Int(readLine()!)!
var nodes = Array(repeating: [Int](), count: N+1)
for _ in 0..<M {
    let pair = readLine()!.split(separator: " ").map{Int(String($0))!}
    nodes[pair[0]].append(pair[1])
    nodes[pair[1]].append(pair[0])
}
var groups = Array(repeating: -1, count: N+1)
var g = 0

func group(_ start: Int)  {
    var queue = [start]
    var q = 0
    if groups[start] != -1 { return }
    while queue.count > q {
        let f = queue[q]
        q += 1
        for next in nodes[f] {
            if groups[next] == -1 {
                groups[next] = g
                queue.append(next)
            }
        }
    }
    if q > 1 {
        g += 1
    }
    
}

for i in 1...N {
    group(i)
}

var represent = Array(repeating: (0,Int.max), count: g)
for i in 1...N {
    if groups[i] != -1 {
        represent[groups[i]].0 = i
    } else {
        represent.append((i,0))
    }
}

func findRepresent(_ start: Int ) {
    var check = Array(repeating: false, count: N+1)
    var queue = [(start,0)]
    var q = 0
    check[start] = true
    var time = 0
    while queue.count > q {
        let f = queue[q]
        q += 1
        time = max(time, f.1)
        for next in nodes[f.0] {
            if check[next] { continue }
            check[next] = true
            queue.append((next, f.1+1))
        }
    }
    if represent[groups[start]].1 > time {
        represent[groups[start]] = (start, time)
    }
}


for i in 1...N {
    if groups[i] == -1 { continue }
    findRepresent(i)
}
print(represent.count)
represent.sorted(by: {$0.0 < $1.0}).forEach {
    print($0.0)
}

 

 

플로이드워셜 사용 

let N = Int(readLine()!)!
let M = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1)
for _ in 0..<M {
    let pair = readLine()!.split(separator: " ").map{Int(String($0))!}
    dp[pair[0]][pair[1]] = 1
    dp[pair[1]][pair[0]] = 1
}

for k in 1...N {
    for i in 1...N {
        for j in 1...N {
            if dp[i][k] == Int.max || dp[k][j] == Int.max {continue}
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
        }
    }
}

var ans = [Int]()
var check = Array(repeating: false, count: N+1)

func group(_ start: Int)  {
    var queue = [start]
    var q = 0
    if check[start] { return }
    check[start] = true
    var list = [start]
    
    while queue.count > q {
        let f = queue[q]
        q += 1
        for i in 1...N {
            if dp[f][i] == Int.max || check[i] { continue }
            check[i] = true
            list.append(i)
            queue.append(i)
        }
    }
    var rep = (Int.max, list.first!)
    list.forEach { x in
        var maxTime = 0
        list.forEach { y in
            if x != y, dp[x][y] != Int.max  {
                maxTime = max(maxTime, dp[x][y])
            }
        }
        if rep.0 > maxTime {
            rep = (maxTime, x)
        }
    }
    ans.append(rep.1)
}

for i in 1...N {
    group(i)
}

print(ans.count)
ans.sorted(by: {$0<$1}).forEach{print($0)}