[C++][백준] 다리 만들기2(17472)

문제

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

 

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

 

풀이

해당 문제는 DFS를 이용한 완전 탐색을 이용하여 풀이하였습니다.

 

첫번째로 1, 0으로 이루어진 맵에서 각 섬들을 구별하기 위해 섬에 넘버링을 해주었습니다.

DFS를 이용하여 간단하게 구현할 수 있습니다.

void dfs(int x, int y, int n) {
	visited[x][y] = true;
	map[x][y] = n;

	for (int i = 0; i < 4; i++) {
		int nextX = x + dirX[i];
		int nextY = y + dirY[i];

		if (IsInRange(nextX, nextY) && map[nextX][nextY] == 1 && visited[nextX][nextY] == false) {
			dfs(nextX, nextY, n);
		}
	}
}	
    
 // 1. 섬에 번호 붙이기
int num = 1;
for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		if (map[i][j] == 1 && visited[i][j] == false) {
			dfs(i, j, num++);
		}
	}
}
numOfIsland = num - 1;

 

두번째로 두 섬을 연결 가능한 다리를 모두 구해줍니다.

다리 방향은 상, 하, 좌, 우만 가능하기 때문에 간단히 구현할 수 있습니다.

인접한 곳이 바다라면 계속 다리를 이어주고 바다가 아니라면 아래 조건을 통해 다리 연결 가능 여부를 확인합니다.

(1) 맵 안에 있으면서

(2) 출발지가 아니면서

(3) 다리 길이가 2 이상

void makeBridge(int x, int y, int from) {
	for (int i = 0; i < 4; i++) {
		int curX = x;
		int curY = y;
		int cnt = 0;
		while (true) {
			int nextX = curX + dirX[i];
			int nextY = curY + dirY[i];

			if (!IsInRange(nextX, nextY)) break;
			else if (map[nextX][nextY] == from) break;
			else if (map[nextX][nextY] == 0) {
				curX = nextX;
				curY = nextY;
				cnt++;
				continue;
			}
			else if (cnt < 2) break;
				
			int to = map[nextX][nextY];
			edges[from][to] = min(cnt, edges[from][to]);
			edges[to][from] = min(cnt, edges[to][from]);
			break;
		}
	}
}

// 2. 섬 X에서 섬 Y를 연결하는 다리 만들기
for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		if (map[i][j] != 0) {
			makeBridge(i, j, map[i][j]);
		}
	}
}

 

세번째로 다리를 연결할 수 있는 모든 경우의 수를 고려해 답을 구합니다.

이 때 1번 다리를 연결하고 3번 다리를 연결하든, 3번 다리를 연결하고 1번 다리를 연결하든 결과는 동일하기 때문에

조합을 사용하여 풀이하였습니다. 

조합 CASE(다리 갯수가 4개인 경우) 0000 // 아무 다리도 연결되어있지 않은 경우 0001 // 4번째 다리만 연결된 경우 0010  0011 // 3번째, 4번째 다리만 연결된 경우 ... 1111 // 모든 다리가 연결된 경우

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
const int MAX = 120;
const int MAX_INT = 987654321;
int map[MAX][MAX];
int edges[8][8];

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

bool visited[MAX][MAX];
bool dfs_visited[8];

int answer = MAX_INT;
int numOfIsland;

struct myData {
	int from;
	int to;
	int cost;
};

vector<myData> edgeList;
int temp[15];

bool IsInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M) return true;
	else return false;
}

void dfs(int x, int y, int n) {
	visited[x][y] = true;
	map[x][y] = n;

	for (int i = 0; i < 4; i++) {
		int nextX = x + dirX[i];
		int nextY = y + dirY[i];

		if (IsInRange(nextX, nextY) && map[nextX][nextY] == 1 && visited[nextX][nextY] == false) {
			dfs(nextX, nextY, n);
		}
	}
}

int min(int a, int b) {
	if (a < b) return a;
	else return b;
}

void makeBridge(int x, int y, int from) {
	for (int i = 0; i < 4; i++) {
		int curX = x;
		int curY = y;
		int cnt = 0;
		while (true) {
			int nextX = curX + dirX[i];
			int nextY = curY + dirY[i];

			if (!IsInRange(nextX, nextY)) break;
			else if (map[nextX][nextY] == from) break;
			else if (map[nextX][nextY] == 0) {
				curX = nextX;
				curY = nextY;
				cnt++;
				continue;
			}
			else if (cnt < 2) break;
				
			int to = map[nextX][nextY];
			edges[from][to] = min(cnt, edges[from][to]);
			edges[to][from] = min(cnt, edges[to][from]);
			break;
		}
	}
}

void init() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			edges[i][j] = MAX_INT;
		}
	}
}

void dfs_check(int n, vector<int> myGraph[10]) {
	dfs_visited[n] = true;

	for (int i = 0; i < myGraph[n].size(); i++) {
		int next = myGraph[n][i];

		if (dfs_visited[next] == false) {
			dfs_check(next, myGraph);
		}
	}
}

void dfs(int x) {
	if (x >= edgeList.size()) {
		// TODO
		vector<int> myGraph[10];
		int totalCost = 0;

		for (int i = 0; i < edgeList.size(); i++) {
			if (temp[i] == 1) {
				int from = edgeList[i].from;
				int to = edgeList[i].to;
				totalCost += edgeList[i].cost;
				
				myGraph[from].push_back(to);
				myGraph[to].push_back(from);
			}
		}

		for (int i = 1; i <= numOfIsland; i++) {
			dfs_visited[i] = false;
		}
		dfs_check(1, myGraph);
		for (int i = 1; i <= numOfIsland; i++) {
			if (dfs_visited[i] == false) {
				return;
			}
		}
		if (totalCost < answer) answer = totalCost;
	}
	else {
		for (int i = 0; i <= 1; i++) {
			temp[x] = i;
			dfs(x + 1);
			temp[x] = 0;
		}
	}
}

int main() {
	init();

	// 1. 섬에 번호 붙이기
	int num = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1 && visited[i][j] == false) {
				dfs(i, j, num++);
			}
		}
	}
	numOfIsland = num - 1;

	// 2. 섬 X에서 섬 Y를 연결하는 다리 만들기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] != 0) {
				makeBridge(i, j, map[i][j]);
			}
		}
	}
	
	// 3. 다리 갯수만큼 완전 탐색
	for (int i = 1; i <= numOfIsland; i++) {
		for (int j = i + 1; j <= numOfIsland; j++) {
			if (edges[i][j] != MAX_INT) {
				edgeList.push_back({ i, j, edges[i][j] });
			}
		}
	}

	dfs(0);

	if (answer == MAX_INT) cout << -1;
	else cout << answer;

	return 0;
}