문제 출처 :
https://www.acmicpc.net/problem/1760
알고리즘 분석 :
문제 해결에 필요한 사항
1. 이분 매칭 :: http://www.crocus.co.kr/499
2. 최대 유량 :: http://www.crocus.co.kr/741
이 문제는 이분 매칭 혹은 최대 유량(유량이 1이라 생각하여) 풀 수 있다.
이번에는 이분 매칭으로 풀 것인데
이 문제는 이분 매칭을 위해 이분 그래프로 나타내는 것이 매우 중요하다.
이 문제를 풀고나면 혹은 이 문제를 풀기 전에
[2414번] 게시판 구멍 막기 :: http://www.crocus.co.kr/750 문제도 풀어보길 추천한다.
문제에서 이분 그래프로 나타내는 방식은 다음과 같다.
3 4 2 0 0 0 2 2 2 1 0 1 0 2
예제 입력을 이용하여 이분 그래프를 만들어보자.
이분 그래프를 만들기 위해 두가지로 명확하게 나뉘는 것은 행, 열이다.
따라서 행렬을 이용한다고 생각하여 이분 그래프를 만들 것이다.
룩은 자신이 위치한 행,열을 공격할 수 있다.
따라서 x,y좌표에 룩이 위치한다면 처음~x~끝,y 그리고 x, 처음~y~끝에는 다른 룩이 올 수 없다.
따라서 그룹화를 다음과 같이 한다.
행 기준으로 넘버링시 ::
1. 0,1이 연속될 경우 같은 그룹으로 넘버링
2. 중간에 2가 있을 시 다른 그룹으로 넘버링(벽이 있으면 룩이 공격을 할 수 없다. 같은 행에 있어도)
열 기준으로 넘버링시 ::
1. 0,1이 연속될 경우 같은 그룹으로 넘버링
2. 중간에 2가 있을 시 다른 그룹으로 넘버링(벽이 있으면 룩이 공격을 할 수 없다. 같은 열에 있어도)
이를 토대로
1-2, 1-4, 1-6, 3-1, 3-5를 연결해준다.
(여기서 연결할 때는 1인 곳에는 놓을 수 없으니, 1인 부분은 이분 매칭에 이용되지 못하도록 한다.)
여기서 매칭을 시켜보면 무슨 일이 일어날까?
열의 1번 행의 3번에 룩이 하나 위치, 열의 2번 행의 1번에 룩이 하나 위치하게 된다.
예제 입력에서도 보면 열의 1번 행의 3번에 룩이 하나 위치, 열의 2번 행의 1번에 룩이 하나 위치하게되면
더이상 위치할 곳이 없게된다.
아래 코드에서 adj가 5002 5002인 이유는
넘버링 시 최악의 경우 5000번까지 생성 될 수 있다.
0 2 0
2 0 2
0 2 0 이런식일때
소스 코드 :
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 | #include <iostream> #include <cstdio> #include <memory.h> #include <vector> #include <algorithm> #define MAX_N 102 using namespace std; int map[MAX_N][MAX_N]; int col[MAX_N][MAX_N]; int row[MAX_N][MAX_N]; bool adj[5002][5002]; vector<int> aMatch; vector<int> bMatch; int visit[5002]; int visitCnt; int n, m; bool dfs(int a) { if (visit[a] == visitCnt) return false; visit[a] = visitCnt; for (int b = 1; b <= m; b++) { if(adj[a][b]) { if (bMatch[b] == -1 || dfs(bMatch[b])) { aMatch[a] = b; bMatch[b] = a; return true; } } } return false; } int bipartiteMatch() { aMatch = vector<int>(n + 1, -1); bMatch = vector<int>(m + 1, -1); int ans = 0; for (int a = 1; a <= n; a++) { visitCnt++; ans += dfs(a); } return ans; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &map[i][j]); int cnt = 1; // 행 기준으로 넘버링 bool chk; for (int i = 1; i <= n; i++) { chk = false; for (int j = 1; j <= m; j++) { if (map[i][j] == 0 || map[i][j] == 1) { col[i][j] = cnt; chk = true; } else if (chk) { cnt++; chk = false; } } if (chk) cnt++; } // 열 기준으로 넘버링 cnt = 1; for (int j = 1; j <= m; j++) { chk = false; for (int i = 1; i <= n; i++) { if (map[i][j] == 0 || map[i][j] == 1) { row[i][j] = cnt; chk = true; } else if (chk) { cnt++; chk = false; } } if (chk) cnt++; } int maxR = 0, maxC = 0; // 2는 당연히 안되고, // 1인 곳도 이분 매칭에 연결되지 않도록 해준다.(룩을 놓을 수 없다.) for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (map[i][j] == 0) { // adj 범위가 여기 때문에 adj[5002][5002]로 설정 adj[row[i][j]][col[i][j]] = 1; maxR = max(maxR, row[i][j]); maxC = max(maxC, col[i][j]); } // 이제는 n,m으로 보는 것이 아닌 넘버링 단위로 봐야한다. n = maxR; m = maxC; int get = bipartiteMatch(); printf("%d", get); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
| [1252번] 이진수 덧셈 (0) | 2017.04.14 |
|---|---|
| [1574번] 룩 어택 (0) | 2017.04.14 |
| [1671번] 상어의 저녁식사 (0) | 2017.04.14 |
| [9576번] 책 나눠주기 (0) | 2017.04.14 |
| [2573번] 빙산 (0) | 2017.04.14 |