백준 17472번 다리 만들기2

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

17472번: 다리 만들기 2

 

 

 

 

 

<접근방법>

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

문제에 대한 감이 아예 안오시면 이 문제를 완전히 이해해야 합니다.

기본적인 그래프 이론 문제입니다.

 

다리를 연결하는 방법을 전부 고려해야하는 완전 탐색 문제입니다.

 

우선 n개의 섬을 전부 연결하기 위해서는 최소 n-1개의 다리가 필요합니다.

즉, 다리 n-1개를 선택해야 합니다.

조합으로 선택하면 됩니다.

 

다리를 선택한 후, 모든 섬이 이어져 있는지 확인해야 합니다.

아무 섬에서 시작하여 bfs를 돌면 확인할 수 있겠죠.

연결여부가 확인되면 최소의 가중치인지 확인하면 됩니다.

 

섬에 번호 붙이기, 가중치 구하기, 연결성 확인...

접근보다는 구현이 어려운 문제였습니다.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

코드에 사족이 많습니다...ㅎㅎ

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

struct point {
	int y, x;
};

const int INF = 987654321;
int n, m, num;
int map[11][11], graph[11][11], w[11][11];
bool selected[11][11];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int res = INF;


void labeling() {
	queue<point> q;
	bool visit[10][10] = {false, };
	num = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && !visit[i][j]) {
				q.push({i, j});
				visit[i][j] = true;

				while (!q.empty()) {
					point t = q.front();
					q.pop();

					graph[t.y][t.x] = num;

					for (int k = 0; k < 4; k++) {
						int ty = t.y + dy[k];
						int tx = t.x + dx[k];



						if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
						if (map[ty][tx] == 0 || visit[ty][tx]) continue;
						
						graph[ty][tx] = num;
						q.push({ty, tx});
						visit[ty][tx] = true;
					}
				}
				num++;
			}
		}
	}
	num--;
}

void distance(int y, int x) {
	int start = graph[y][x];
	for (int i = 0; i < 4; i++) {
		int ty = y;
		int tx = x;
		int len = 0;
		int next;

		while (1) {
			ty += dy[i];
			tx += dx[i];

			if (ty < 0 || ty >= n || tx < 0 || tx >= m) break;
			if (graph[ty][tx] == start) break;
			
			next = graph[ty][tx];
			if (next != 0) {
				if (len >= 2) {
					w[start][next] = min(w[start][next], len);
				}
				break;
			}
			len++;
		}
	}
}

void cal_weight() {
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++) {
			w[i][j] = INF;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (graph[i][j] != INF) {
				distance(i, j);
			}
		}
	}

	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++) {
			if (w[i][j] == INF) {
				w[i][j] = 0;
			}
		}
	}
}

bool check() {
	queue<int> q;
	bool visit[10] = { false, };
	int cnt = 0;

	q.push(1);
	visit[1] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cnt++;

		for (int i = 1; i <= num; i++) {
			if (visit[i]) continue;
			if (selected[now][i]) {
				q.push(i);
				visit[i] = true;
			}
		}
	}
	if (cnt == num) return true;
	return false;
}

void dfs(int dep, int start, int W) {
	if (dep == num - 1) {
		if (check()) {
			res = min(res, W);
		}
		return;
	}

	for (int i = start; i < num*num; i++) {
		int y = i / num + 1;
		int x = i % num + 1;

		if (y <= x) continue;

		if (w[y][x] != 0) {
			selected[y][x] = true;
			selected[x][y] = true;
			dfs(dep + 1, i + 1, W + w[y][x]);
			selected[y][x] = false;
			selected[x][y] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	labeling();
	cal_weight();
	dfs(0, 0, 0);

	if (res == INF) cout << -1 << '\n';
	else cout << res << '\n';

	return 0;
}