백준 17472 다리 만들기 2

 

17472번: 다리 만들기 2

 

 

/* 1. 빈칸과 이웃한 경우 뿐만 아니라 경계에 해당하는 경우에도 boundary에 해당함 */
/* 2. 행과 열의 상한 다름 -> N <> M */
/* 3. 탈출조건은 b < bound[island_ctr]이 아니라 b < bound_ctr[i] */
/* 4. 가장 최근에 계산한 다리 길이가 아니라 가장 짧은 다리 길이로 갱신 */
/* 5. dfs로 네트워크형 그래프 연결여부 파악하려면 전역변수로 visited_vertices 선언하여 방문시 갱신 */
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int N, M;
bool map[10][10];
int island_no[10][10], island_ctr;
int bound_coord[100][100][2], bound_ctr[100];
unsigned cst[6][6];
unsigned ans = -1;
// dfs1
bool vst1[10][10];
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void dfs1(int r, int c) {
	vst1[r][c] = 1;
	island_no[r][c] = island_ctr;
	bool is_bound = false;
	for (int d = 0; d < 4; ++d) {
		int nr = r + dr[d], nc = c + dc[d];
		if (0 <= nr && nr < N && 0 <= nc && nc < M && map[nr][nc]) {
			if (!vst1[nr][nc]) {
				dfs1(nr, nc);
			}
		}
		else {	/* 1 */
			is_bound = true;
		}
	}
	if (is_bound) {
		bound_coord[island_ctr][bound_ctr[island_ctr]][0] = r;
		bound_coord[island_ctr][bound_ctr[island_ctr]][1] = c;
		++bound_ctr[island_ctr];
	}
}
// dfs2
int vst[6], vstn;
int islands_visited;
bool adj[6][6];
void dfs2(int u) {
	vst[u] = vstn;
	++islands_visited;
	for (int v = 0; v < island_ctr; ++v) {
		if (adj[u][v] && vst[v] != vstn) {
			dfs2(v);
		}
	}
}
void bf(int u, int v, int s, unsigned sum_cst) {
	if (s == island_ctr - 1) {
		++vstn;
		islands_visited = 0;
		dfs2(0);
		if (islands_visited == island_ctr && sum_cst < ans) {
			ans = sum_cst;
		}
		return;
	}
	for (; u < island_ctr; ++u) {
		for (; v < island_ctr; ++v) {
			if (cst[u][v] != -1) {
				adj[u][v] = adj[v][u] = 1;
				bf(u, v + 1, s + 1, sum_cst + cst[u][v]);
				adj[u][v] = adj[v][u] = 0;
			}
		}
		v = u + 2;
	}
}
int main() {
	memset(island_no, -1, sizeof(island_no));
	memset(cst, -1, sizeof(cst));
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int r = 0; r < N; ++r) {
		for (int c = 0; c < M; ++c) {
			cin >> map[r][c];
		}
	}
	for (int r = 0; r < N; ++r) {
		for (int c = 0; c < M; ++c) {
			if (map[r][c] && !vst1[r][c]) {
				dfs1(r, c);
				++island_ctr;
			}
		}
	}
	for (int u = 0; u < island_ctr; ++u) {
		for (int b = 0; b < bound_ctr[u]; ++b) {
			int r = bound_coord[u][b][0], c = bound_coord[u][b][1];
			for (int d = 0; d < 4; ++d) {
				int nr = r + dr[d], nc = c + dc[d];
				if (map[nr][nc]) {
					continue;
				}
				for (; 0 <= nr && nr < N && 0 <= nc && nc < M && !map[nr][nc]; nr += dr[d], nc += dc[d]);
				if (nr < 0 || N <= nr || nc < 0 || M <= nc) {
					continue;
				}
				int v = island_no[nr][nc];
				if (abs(nr - r) + abs(nc - c) - 1 > 1 && abs(nr - r) + abs(nc - c) - 1 < cst[u][v]) {	/* 4 */
					cst[u][v] = cst[v][u] = abs(nr - r) + abs(nc - c) - 1;
				}
			}
		}
	}
	bf(0, 0, 0, 0);
	cout << (int)ans;
	return 0;
}