문제 출처 :
https://www.acmicpc.net/problem/1014
알고리즘 분석 :
문제 해결에 필요한 사항
1. 최대 독립 집합
2. 최소 버텍스 커버 :: http://www.crocus.co.kr/756
3. 이분 매칭 :: http://www.crocus.co.kr/499
이 문제는 컨닝을 할 수 있는 자리와 컨닝을 당하는 자리를 매칭해주게 되는 방법을 이용하여 풀 수 있는 문제이다.
아래 그림을 보자.
특정 부분의 주황색 정점에 대해 컨닝할 수 있는 부분을 모두 표시해두었다.
푸른색 6점에서 주황색 하나의 정점과 컨닝을 할 수 있는 관계가 형성된다.
첫번째 정점을 순서대로
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15 정점이라 생각해보자.
이때 0-1, 2-3, 4-5, 6-7, 8-9, 10-11, 12-13, 14-15가 연결 시키게 된다면
이 의미는 총 8자리에만 컨닝을 하지 못하게 앉힐 수 있다는 의미이다.
연결의 의미는 주황색 정점과 푸른색 정점이 연결되는 순간 푸른색 정점에서 주황색 정점으로 혹은 주황색 정점에서 푸른색 정점으로
컨닝을 할 수 있다는 의미가 된다.
따라서 이 문제는 주황색과 푸른색을 하나씩만 연결해주면 되는 문제이고, 결국 최대 독립 집합 문제로 이어진다.
최대 독립 집합의 정의는 집합에 포함된 모든 정점끼리를 연결하는 Edge가 없어야 하므로
결국 최소 버텍스 커버의 여집합이 된다.
최소 버텍스 커버는 위의 링크에서 확인 할 수 있듯이 쾨닉의 정리에 의해 이분 그래프로 표현할 수 있고, 이분 매칭으로 풀 수 있다.
이 문제는 DP로도 풀 수 있다고 알려져 있으나, 이 문제를 이분 매칭으로 해결해 낸다면
[11014번] 컨닝 2 :: https://www.acmicpc.net/problem/11014 문제에서 정점의 수만 변경해 준다면 바로 AC를 받을 수 있다.
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> #include <cstdio> #include <vector> #define MAX_N 15 using namespace std; int n, m; char map[MAX_N][MAX_N]; int number[MAX_N][MAX_N]; vector<int> visit; int visitCnt = 1; vector<int> aMatch; vector<int> bMatch; vector<int> point; vector<vector<int>> adj; int dy[6] = { -1,-1,0,0,1,1 }; int dx[6] = { -1,1,-1,1,-1,1 }; bool dfs(int a) { if (visit[a] == visitCnt) return false; visit[a] = visitCnt; for (int i = 0; i < adj[a].size(); i++) { int b = adj[a][i]; if (bMatch[b] == -1 || dfs(bMatch[b])) { aMatch[a] = b; bMatch[b] = a; return true; } } return false; } int bipartiteMatch() { int size = 0; visit = vector<int>(n*m + 1); aMatch = vector<int>(n*m + 1, -1); bMatch = vector<int>(n*m + 1, -1); for (int a = 0; a < point.size(); a ++) { visitCnt++; size += dfs(point[a]); } return size; } int main() { int tc; scanf("%d", &tc); while (tc--) { scanf("%d %d", &n, &m); adj = vector<vector<int>>(n*m+1); point.clear(); int crash = 0; for (int i = 0; i < n; i++) scanf("%s", map[i]); int cnt = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { // x의 개수 count if (map[i][j] == 'x') crash++; // i를 기준으로 짝수 / 홀수로 이분매칭을 한다. // 이때 짝수 위치를 point벡터에 담아둔다. if (j % 2 == 0) point.push_back(cnt); // 정점의 (i,j)를 cnt로 넘버링 number[i][j] = cnt++; } // i가 짝수번째인 정점에서 컨닝 할 수 있는 모든 위치를 adj에 push for(int i = 0 ; i < n; i ++) for (int j = 0; j < m; j += 2) { if (map[i][j] == 'x') continue; for (int k = 0; k < 6; k++) { int y = i + dy[k]; int x = j + dx[k]; if (x < 0 || y < 0 || x >= m || y >= n || map[y][x] == 'x') continue; adj[number[i][j]].push_back(number[y][x]); } } // 이분 매칭 int ans = bipartiteMatch(); printf("%d\n", n*m - ans - crash); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[10159번] 저울 (0) | 2017.04.25 |
---|---|
[11014번] 컨닝 2 (0) | 2017.04.24 |
[1431번] 시리얼 번호 (0) | 2017.04.24 |
[5651번] 완전 중요한 간선 (0) | 2017.04.24 |
[1074번] Z (0) | 2017.04.22 |