백준 1671 상어의 저녁식사
23 Jun 2021https://www.acmicpc.net/problem/1671
상어가 본인보다 능력치가 낮거나 같은 다른 상어를 2마리까지 잡어먹을 수 있다고 했을 때 살아남을 수 있는 상어의 최솟값을 구하는 문제이다. 지금까지는 이분 매칭에서 두 그룹이 서로 다른 경우를 풀었었다면 이번 문제의 경우는 두 그룹이 같은 경우의 문제이다. 까다로워 보이지만 2가지만 유의해서 문제를 풀어보자.
- 두마리를 잡아먹을 수 있다는 부분은 같은 상어에 대해 2번의 dfs를 해주면 된다.
- 능력치가 같다면 서로를 잡아먹을 수 있기 때문에 이 경우 index가 낮은 상어가 높은 상어를 잡아먹도록 한다.
그 외에는 일반적인 이분매칭 문제와 똑같기 때문에 두가지만 유의해주면 된다.
- 전체 코드
let n = Int(readLine()!)!
var shark:[(Int, Int, Int)] = []
var visited:[Bool] = Array(repeating: false, count: n)
var eater:[Int] = Array(repeating: -1, count: n)
for _ in 0..<n {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
shark.append((line[0], line[1], line[2]))
}
func dfs(idx: Int) -> Bool {
for i in 0..<n where i != idx {
if visited[i] {
continue
}
if shark[i].0 <= shark[idx].0 && shark[i].1 <= shark[idx].1 && shark[i].2 <= shark[idx].2 {
if shark[i] == shark[idx] && idx >= i {
continue
}
visited[i] = true
if eater[i] == -1 || dfs(idx: eater[i]) {
eater[i] = idx
return true
}
}
}
return false
}
var result = 0
for i in 0..<n {
visited = Array(repeating: false, count: n)
if dfs(idx: i) {
result += 1
}
visited = Array(repeating: false, count: n)
if dfs(idx: i) {
result += 1
}
}
print(n-result)