[1799번] 비숍

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭 :: http://www.crocus.co.kr/499

이 문제를 풀고 있다면 룩 시리즈 문제를 꼭 풀어보길 바란다.

룩 시리즈 문제 :: http://www.crocus.co.kr/search/rook

체스판 문제는 이분 매칭 문제로 연결 할 수 있고, 룩, 비숍 등등 문제 접근법만 알아낸다면 똑같은 코드가 계속 재활용된다.

룩의 경우에는 행 / 열에 대해 넘버링을 하여 이분 매칭을 하지만,

비숍의 경우에는 대각선으로 움직이기에 대각선을 기준으로 넘버링을 해야한다.

넘버링 이후 이제 벽이 아닌 것들에 대해 이분 그래프를 형성해 주면 된다.

위의 그래프를 토대로 이분 그래프를 형성 한 후 아래 이분 매칭을 하게되면 예제 입력 값의 결과가 된다.

즉, 왼쪽 그래프의 1번과 오른쪽 그래프의 5번이 있는 곳에 비숍을 놓으면 된다는 의미가 되는 것이다.

(그렇게 계속 반복)

소스 코드 : 

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 153 154 155 156 157 158 159 160 161 162 163

#include <iostream> #include <cstdio> #include <vector>   #define max(a,b)(a > b ? a : b) #define MAX_N 52 #define MAX_V 102 using namespace std;   vector<int> adj[MAX_V]; vector<int> aMatch; vector<int> bMatch;   int map[MAX_N][MAX_N]; int visit[MAX_V]; int visitCnt;   int Left[MAX_N][MAX_N]; int Right[MAX_N][MAX_N];   int n, m;   void fillLeft(); void fillRight(); void checkLeftandRight();   bool dfs(int a) {     if (visit[a] == visitCnt)         return false;       visit[a] = visitCnt;       for (int next = 0; next < adj[a].size(); next++)     {         int b = adj[a][next];           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 size = 0;       for (int a = 1; a <= n; a++)     {         visitCnt++;         size += dfs(a);     }       return size; }   int main() {     scanf("%d", &n);       for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++)             scanf("%d", &map[i][j]);       fillLeft();     fillRight();     // checkLeftandRight();       // 1일때만 간선 연결(0일때는 벽이니)     int maxL = 0, maxR = 0;       for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++)             if (map[i][j] == 1)             {                 adj[Left[i][j]].push_back(Right[i][j]);                   maxL = max(maxL, Left[i][j]);                 maxR = max(maxR, Right[i][j]);             }       // 이분매칭에 이용 될 n과 m은 maxL, maxR로 교체된다.     n = maxL;     m = maxR;           int get = bipartiteMatch();     printf("%d", get);       return 0; }     void fillLeft() {     int y = 1;     int x = n;     int cnt = 1;       // 오른쪽 위 시작 기준 대각선은 총 n번 반복     for (int k = 0; k < 2*n-1; k++)     {         int tmpy = y;         int tmpx = x;           while (tmpy <= n)             Left[tmpy++][tmpx++] = cnt;           cnt++;         x--;     } }   void fillRight() {     int y = n;     int x = n;     int cnt = 1;       // 오른쪽 아래 시작 기준 대각선은 총 n번 반복     for (int k = 0; k < 2*n-1; k++)     {         int tmpy = y;         int tmpx = x;           while (tmpy > 0)                 Right[tmpy--][tmpx++] = cnt;           cnt++;         x--;     } }   void checkLeftandRight() {     cout << endl;     for (int i = 1; i <= n; i++)     {         for (int j = 1; j <= n; j++)             cout << Left[i][j] << " ";         cout << endl;     }       cout << endl;       for (int i = 1; i <= n; i++)     {         for (int j = 1; j <= n; j++)             cout << Right[i][j] << " ";         cout << endl;     } }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus