이분 매칭을 2번 작동하면 된다.
글을 작성하다 날려서 더 길게 적고싶지 않다.
| BOJ 백준온라인져지 10159 저울 풀이 (0) | 2018.02.01 |
|---|---|
| BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이 (0) | 2018.01.30 |
| BOJ 백준온라인져지 2822 점수 계산 풀이 (0) | 2018.01.25 |
| BOJ 백준온라인져지 11375 열혈강호 풀이 (0) | 2018.01.23 |
| BOJ 백준온라인져지 14502 연구소 풀이 (0) | 2018.01.14 |
이분 매칭 문제를 엄청 오랜만에 풀어봤다.
https://en.wikipedia.org/wiki/Matching_(graph_theory)
http://koosaga.com/18
http://1ambda.github.io/algorithm/algorithm-part2-5/
위 링크에 많은 설명이 있고, 읽지는 않았다.
이 문제를 풀이한 방법은 아주 기초적인 DFS 를 이용한 O(V * E) 이다.
오늘은 시간이 없어서 이론보다는 구현을 목적으로 공부했다.
풀이 방법
1. 사람을 한명씩 dfs 로 연결할 수 있는 일을 잡는다.
2. 이미 연결돼있는 선이라면 그 선에 연결된 사람이 다른 일을 잡을 수 있는지 확인한다.
3. 반복
4. 끝
| BOJ 백준온라인져지 11376 열혈강호 2 풀이 (0) | 2018.01.27 |
|---|---|
| BOJ 백준온라인져지 2822 점수 계산 풀이 (0) | 2018.01.25 |
| BOJ 백준온라인져지 14502 연구소 풀이 (0) | 2018.01.14 |
| BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 (0) | 2018.01.13 |
| BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0) | 2018.01.11 |