백준 1867 돌멩이 제거

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

n행 n열로 나뉜 운동장이 주어졌을 때 k개의 돌멩이가 있다고 하자. 한번에 1개의 행 혹은 1개의 열에 있는 돌멩이를 모두 치울 수 있다고 했을 때 최소한의 횟수로 돌멩이를 모두 치우는 방법을 구하는 문제이다. 쾨닉의 정리라는 기법을 사용해야 하는데 쾨닉의 정리에 대해 알아보기 전에 Vertex Cover에 대해 알아보자.

1. Vertex Cover

Vertex Cover : 정점 집합 S가 있을 때, 모든 간선의 양 끝점 중 하나가 S에 포함되어 있는 집합 S

예를 들어 다음 그래프의 경우 Vertex Cover 중 하나는 {A, B}에 해당한다.

Minimum Vertex Cover란 Vertex Cover 중 최소 길이의 집합을 의미한다. 위 그림의 경우 Vertex Cover로는 여러가지가 있겠지만 {A, B}가 최소의 길이를 갖는다.

2. 쾨닉의 정리

자 이제 쾨닉의 정리에 대해 알아보자. 증명까지는 안다루지만 이분 그래프의 최대 매칭을 구하면 모든 간선을 cover할 수 있다는 의미가 된다.

쾨닉의 정리 : 이분 그래프에서의 최대 매칭은 minimum vertex cover와 같다.

자 그러면 우리의 문제를 이분매칭 그래프로 표현해보자.

먼저 행과 열을 각각의 집합으로 생각하고 돌멩이가 위치한 행과 열 사이에 간선을 그려준다. 그렇게 되면 간선 하나당 돌멩이 하나를 의미하게 된다. 모든 돌멩이(간선)를 cover 할 수 있는 최소한의 정점은 달리기를 해야하는 행과 열을 각각 의미하게 된다. 따라서 쾨닉의 정리에 의해 최대 매칭을 구해주면 달리기 횟수를 구할 수 있다.

• 전체 코드

let nk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nk[0], k = nk[1]
var row2col:[Int] = Array(repeating: -1, count: n+1)
var edge:[[Int]] = Array(repeating: [], count: n+1)
var visited:[Bool] = Array(repeating: false, count: n+1)
for _ in 0..<k {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    edge[line[0]].append(line[1])
}
func dfs(col: Int) -> Bool {
    for row in edge[col] {
        if visited[row] {
            continue
        }
        visited[row] = true
        if row2col[row] == -1 || dfs(col: row2col[row]) {
            row2col[row] = col
            return true
        }
    }
    return false
}
var r = 0
for i in 1...n {
    visited = Array(repeating: false, count: n+1)
    if dfs(col: i) {
        r += 1
    }
}
print(r)