[ 백준-17472번 / 그래프 / MST / 완전탐색 ] 다리만들기2

1. 문제

---

 

17472번: 다리 만들기 2

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

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

출력

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

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

예제 입력 1 복사

7 8 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

예제 출력 1 복사

9

 

 

2. 소스코드

---

1회차

 

- BFS로 섬을 나누고, 다리가 될 수 있는 위치를 파악함. 그 뒤 앞의 두 정보로 인접행렬을 만들고, MST를 구해서 해결함.

- 인접행렬을 구하고 MST 개념을 전혀 몰라서, 시간이 많이 걸렸던 문제. 만들고 보니 MST라는 개념이라더라.

- MST를 구하는 함수는 큰 틀은 프림 알고리즘과 같으나, 프림 알고리즘을 모르고 짰기에 조금 비효율적임.

- 이 문제에서는 인접행렬이 인접리스트 보다 효율적이다. 최소 경로 단 하나만 저장하면 되기 때문. 인접행렬을 이용해 코딩해 볼 것.

- 굳이 MST로 풀지 않아도 되는 듯 하다.

 

- 인접리스트를 만드는 함수를 다른 사람의 코드를 참조해 수정했다. 기존에는 4방향으로 4번 하드코딩했는데, 간결하고 좋은 방법인 것 같다.

void makeAdjArr(int x, int y, int idx) {
 
	for (int k = 0; k < 4; ++k) {
		int dist = 0;
		int nx = x + dx[k];
		int ny = y + dy[k];
        //바다이거나, 범위 내 인경우 계속 탐색.
		while (map[nx][ny] == SEA and nx >= 0 and ny >= 0 and nx < n and ny < m)
		{//한 방향으로 계속 더해본다.
			nx += dx[k];
			ny += dy[k];
			dist++;
		}//다리 길이가 2이상이고, nx,ny가 범위 내인 경우.
        //같은 구역 땅인 경우는 상관없다. 같은 땅인 경우 무조건 dist가 1이하이므로 걸러진다.
		if (dist >= 2 and nx >= 0 and ny >= 0 and nx < n and ny < m) {
			adj[map[x][y]].push_back({ map[nx][ny],dist });
			adj[map[nx][ny]].push_back({ map[x][y] ,dist });
		}
	}
}

 

#pragma warning (disable : 4996)
#include <cstdio>
#include <queue>
#include <vector>

#define SEA 7
#define LAND -1

using namespace std;

int map[10][10];
int n, m, landIdx, ans = 1000;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<pair<int, int>> adj[6];
 
void divideLand(int x, int y, int idx) {
	int visited[10][10] = { 0, };
	visited[x][y] = 1;
	map[x][y] = idx;
	queue<pair<int, int>> que;
	que.push({ x,y });
	while (!que.empty())
	{
		int curX = que.front().first;
		int curY = que.front().second;
		que.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = curX + dx[i];
			int ny = curY + dy[i];
			if (nx >= n or ny >= m or nx < 0 or ny < 0) continue;
			if (visited[nx][ny] == 1 or map[nx][ny] == SEA) continue;
			que.push({ nx,ny });
			visited[nx][ny] = 1;
			map[nx][ny] = idx;
		}
	}
}
void makeAdjArr(int x, int y, int idx) {
 
	for (int k = 0; k < 4; ++k) {
		int dist = 0;
		int nx = x + dx[k];
		int ny = y + dy[k];
		while (map[nx][ny] == SEA and nx >= 0 and ny >= 0 and nx < n and ny < m)
		{
			nx += dx[k];
			ny += dy[k];
			dist++;
		}
		if (dist >= 2 and nx >= 0 and ny >= 0 and nx < n and ny < m) {
			adj[map[x][y]].push_back({ map[nx][ny],dist });
			adj[map[nx][ny]].push_back({ map[x][y] ,dist });
		}
	}
}
void findMST() {
	int visited[6] = { 0, };
	visited[0] = 1;
	int res = 0;
	vector <int> nodes;
	nodes.push_back(0);
	//0번 노드부터 시작한다.
	for (int k = 0; k < 6; ++k) {
		int minDist = 100;
		int nextNode = -1;
		//현재 방문한 노드에서 갈 수 있는 노드 중 가장 가까운 길을 선택한다.
		for (int i = 0; i < nodes.size(); ++i) {//방문한 노드
			int curNode = nodes[i];
			for (int j = 0; j < adj[curNode].size(); ++j) {
				if (minDist > adj[curNode][j].second and visited[adj[curNode][j].first] == 0) {
					nextNode = adj[curNode][j].first;
					minDist = adj[curNode][j].second;
				}
			}
		}
		// 방문처리를 한다. 방문한 노드에 포함한다.
		if (nextNode != -1) {
			visited[nextNode] = 1;
			nodes.push_back(nextNode);
			res += minDist;
		}
	}
	// 모두 이어졌는가? 정답을 갱신한다.
	if (nodes.size() == landIdx) ans = res;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) map[i][j] = LAND;
			else map[i][j] = SEA;
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (map[i][j] == LAND) {
				divideLand(i, j, landIdx);
				landIdx++;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (map[i][j] != SEA) {
				makeAdjArr(i, j, map[i][j]);
			}
		}
	}
	
	findMST();

	if (ans == 1000) printf("-1");
	else printf("%d", ans);

	return 0;
}