boj 1867 - 돌맹이 제거

 

개요

Vertex Cover 문제입니다. 단, bipartite matching에서의 minimum vertex cover는 쾨닉의 정리에 의해서 maximum bipartite matching과 그 수가 같습니다. 결과적으로 이분매칭 알고리즘 응용입니다. 

 

쾨닉의 정리는 다음 블로그 포스트를 참고하면서 공부했습니다.

https://gazelle-and-cs.tistory.com/12

https://m.blog.naver.com/kks227/220967185015

 

그런데 이분매칭 알고리즘이라고 하더라도, 문제를 처음보면 이게 어떻게 이분매칭으로 변환될 수 있지? 라는 생각이 들긴 합니다. 시간을 약간 쓰면 퍼즐 풀 듯이 이분 매칭으로 치환하는 방법이 눈에 보였었습니다.

 

예제

백준 예제는 그대로 차용하기에 단순해서 조금 더 큰 예시를 들어보겠습니다.

x _ _ _
x _ x _
x x x x
x _ _ _

 

돌멩이를 줍는 과정은 가로 혹은 세로로 직선 움직임을 통해서 줍습니다. 즉, 돌멩이는 최소한 한 번의 가로 혹은 세로 움직임을 통해서 처리가 되어야 합니다.

 

여기서 가로의 움직임을 $V_L$, 세로의 움직임을 $V_R$, 그리고 돌멩이들을 간선으로 치환할 수 있습니다.

 

Vertex Cover

Vertex Cover는 그래프에서 몇 개의 Vertex를 골랐을 때 ($V_{cover}$), 그래프에 속한 모든 edge의 양 끝 vertex $(x,y)$에 대해 $x \in V_{cover}$ 혹은 $y \in V_{cover}$임을 의미합니다.

 

아래 예제를 통해서 간단히 보겠습니다.

Vertex Cover로서

 (1) 3과 A를 고른 경우: 검은색 edge (2,C)의 양 끝 vertex 2와 C가 둘 다 vertex cover에 속하지 않기 때문에 vertex cover가 아닙니다.

 

 (2) 2, 3, A를 고른 경우: 모든 edge가 조건을 갖추고 있습니다. 그리고 이 선택지가 최소의 vertex cover 개수입니다. (유일하지 않습니다. A, 3, C를 골라도 됩니다.)

 

 (3) 1, 2, 3, 4, A, B, C를 고른 경우: 역시 vertex cover입니다. 하지만 최소는 아닙니다.

 

 

돌멩이 제거

 백준의 문제에서는 edge가 돌멩이였습니다. 그리고 이 돌멩이를 처리하기 위해서 어느 직선으로 움직일지 결정하는 것은 vertex를 고르는 것과 동일합니다. 그리고 edge들을 모두 처리하기 위해서는 결국 vertex cover 문제와 동일하게 되고, 움직임의 최소 횟수를 찾아야 하므로 minimum vertex cover 문제가 됩니다.

 e.g.) 2번 노드를 vertex cover로서 선택하는 것은... 

→ 2번 열의 가로방향으로 움직인다는 것을 의미 

→ 돌멩이 (2, A) 와 (2, C)를 처리할 수 있음 

→ edge (2, A)와 edge (2, C)가 처리 됨

 

 

 

 

 

 

 

쾨닉의 정리

 이분 매칭 그래프에서 minimum vertex cover의 값은 maximum bipartite maching의 값과 같다는 정리입니다. 증명은 맨 위 상단 두 블로그를 통해서 확인하시면 될 것 같습니다!

 

 따라서 이분 매칭 알고리즘을 이용해서 최대의 이분 매칭 개수를 구하면 그 값이 정답이 됩니다.

 

 좌측은 최대 이분매칭을 나타낸 그래프고, 오른쪽은 그 이분매칭을 기반으로하여 Vertex Cover를 선택한 것입니다.

 

정답은 3.

 

코드

RUST

use std::io::{stdin, Read};

fn dfs(i: usize, graph: &Vec<Vec<usize>>, parent: &mut [usize; 501], visited: &mut [bool; 501]) -> usize{
    for next in graph[i].iter(){
        if visited[*next] {
            continue;
        }
        visited[*next] = true;
        if parent[*next] == 0 || dfs(parent[*next], graph, parent, visited) == 1{
            parent[*next] = i;
            return 1;
        }
    }
    return 0;
}
fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>);

    let n = input.next().unwrap();
    let k = input.next().unwrap();

    let mut graph: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
    for _k in 1..(k + 1){
        let a = input.next().unwrap();
        let b = input.next().unwrap();
        graph[a].push(b);
    }
    
    let mut ANS = 0;
    let mut parent: [usize; 501] = [0; 501];
    for _n in 1..(n + 1){
        let mut visited: [bool; 501] = [false; 501];
        ANS += dfs(_n, &graph, &mut parent, &mut visited);
    }
    println!("{ANS}");
}