백준 17472 다리 만들기 2

문제 링크:

불러오는 중입니다...

코드:

/* 1. visited 체크 누락 */
/* 2. boundary */
/* 3. 배열 boundary chk시에는 왠만하면 < 부호 쓰기 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };

int N, M;
vector<pair<int, int>> isl;
bool map1[12][12];
int map2[12][12];
int V = 1;
int cst[7][7];
set<pair<int, int>> cnct;
bool cbn[15], adj[7][7], vst[7];
int v, CST, ans = 50;

void DFS1(int n, int m) {
	map1[n][m] = 0;    /* 1 */
	map2[n][m] = V;
	for (int d = 0; d < 4; ++d) {
		int cn = n + dn[d], cm = m + dm[d];
		if (!map1[cn][cm])
			continue;
		DFS1(cn, cm);
	}
}

void DFS2(int n, int m) {
	map1[n][m] = 0;
	int u = map2[n][m];
	for (int d = 0; d < 4; ++d) {
		int cn = n + dn[d], cm = m + dm[d];
		if (map1[cn][cm]){
            if(map2[cn][cm] == u)
			    DFS2(cn, cm);
            else if(!map2[cn][cm]){
                int c = 1;
                for (cn += dn[d], cm += dm[d]; map1[cn][cm] && !map2[cn][cm]; cn += dn[d], cm += dm[d])
                    ++c;
                int w = map2[cn][cm];
                if (w != 0 && w != u && (!cst[u][w] || (cst[u][w] && c < cst[u][w])) && c >= 2) {
                    cst[u][w] = cst[w][u] = c;
                    cnct.insert({ u, w });
                }
            }
        }
	}
}

void DFS3(int i) {
	++v;
	vst[i] = 1;
	for (int j = 1; j <= V; ++j)
		if (adj[i][j] && !vst[j])
			DFS3(j);
}

int main() {
	cin >> N >> M;
	for (int n = 1; n <= N; ++n) {
		for (int m = 1; m <= M; ++m) {
			cin >> map1[n][m];
			if (map1[n][m])
				isl.emplace_back(n, m);
		}
	}

	for (auto p : isl) {
		if (!map1[p.first][p.second])
			continue;
		DFS1(p.first, p.second);
		++V;
	}
	--V;

	for (int n = 1; n < N + 1; ++n)    /* 3. */
		fill(map1[n] + 1, map1[n] + M + 1, 1);    /* 2. M이 아니라 M + 1 */

	for (auto p : isl) {
		if (!map1[p.first][p.second])
			continue;
		DFS2(p.first, p.second);
	}

	int E = cnct.size();
	fill(cbn, cbn + E, 0);
	for (int c = E - 1; c >= E - V + 1; --c)
		cbn[c] = 1;
	do {
		for (int u = 1; u < V + 1; ++u)
			fill(adj[u] + 1, adj[u] + V + 1, 0);     /* 2. V가 아니라 V + 1 */
		int c = 0;
		CST = 0;
		for (auto p : cnct) {
			int i = p.first, j = p.second;
			if (cbn[c++]) {
				adj[i][j] = adj[j][i] = 1;
				CST += cst[i][j];
			}
		}
		v = 0;
		fill(vst + 1, vst + V + 1, 0);
		DFS3(1);
		if (v == V && CST < ans)
			ans = CST;
	} while (next_permutation(cbn, cbn + E));

	if (ans == 50)	cout << -1;
	else			cout << ans;
	return 0;
}

 

생긴지 얼마 되지 않은 문제이기도 하고, 풀이가 복잡해서 그런지

숏코딩용 편집을 하지 않았음에도 불구하고 숏코딩 순위 안에 포함되었다.