백준 17472 - 다리 만들기 2

문제링크

• 백준 17472

문제설명

• NxM 크기의 격자판에 바다(0), 땅(1) 이 주어진다.
• 인접한 땅끼리는 하나의 섬을 이룬다.
• 섬과 섬 사이에는 다리를 둘 수 있는데, 다리는 가로 막대 혹은 세로 막대 형태여야 한다.
• 모든 섬을 연결하도록 다리를 둘 때, 다리 길이의 합의 최솟값을 구하라.

문제접근

• BFS를 통해 섬의 번호를 메긴다.
  • 입력으로 받는 격자판의 정보에서 땅(1)을 -1로 바꾸어 저장해둔다.
  • 섬 번호가 정해지지 않은 땅(-1)은 BFS를 통해 섬 번호를 정해준다.
• 섬과 섬 사이에 다리를 둘 때 필요한 비용을 계산한다.
  • 섬의 좌표에서 다리는 4가지 방향으로 만들 수 있다.
  • 같은 섬에 속하는 좌표에는 다리를 둘 수 없다.
  • 격자판을 벗어나는 경우는 다리를 둘 수 없다.
  • 다리 길이는 2 이상이어야 한다.
  • 섬의 연결 가능 여부를 파악하는 linked 배열을 통해 다리를 모두 두었을 때 연결되지 않은 섬이 있는 경우 -1 을 출력하고 로직을 종료한다.
  • costs 2차원 배열을 만들어서 costs[0]: from, cost[1]: to, costs[2]: weight 로 테이블을 만든다.
• 최소신장트리(MST)를 찾는다. (크루스칼 알고리즘)
  • costs 테이블을 비용이 적은 순서대로 오름차순 정렬한다.
  • group 배열을 만들어서 각 섬의 그룹을 할당한다.
  • costs 테이블을 탐색하며 두 섬의 그룹이 서로 다르다면 연결하고, 그룹 번호가 작은 번호로 두 섬을 합친다.
• 하나의 그룹에 속하지 않은 경우 -1 을 출력한다.
• 하나의 그룹에 속한 경우 누적된 비용을 출력한다.

구현

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

int N, M;
int land[10][10];
bool visited[10][10];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<vector<int>> costs; // costs[0]: from, costs[1]: to, costs[2]: weight
int countIsland;

void printLand() {
	printf("--------------------------\n");
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			printf("%d ", land[r][c]);
		}
		printf("\n");
	}
}

void printGraph() {
	printf("############################\n");
	for (int i = 0; i < costs.size(); i++) {
		printf("from: %d, to: %d, weight: %d\n", costs[i][0], costs[i][1], costs[i][2]);
	}
}

// 섬 번호를 메기기 위한 BFS
void bfsIsland(int x, int y, int area) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	land[x][y] = area;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
			if (land[nextX][nextY] == 0) continue;
			if (visited[nextX][nextY]) continue;
			visited[nextX][nextY] = true;
			q.push(make_pair(nextX, nextY));
			land[nextX][nextY] = area;
		}
	}
}

// 섬의 번호를 메긴다.
void setIsland() {
	int area = 0;
	memset(visited, false, sizeof(visited));
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (land[r][c] == -1) {
				bfsIsland(r, c, ++area);
			}
		}
	}
	countIsland = area;
	// printLand();
}

// 섬과 섬을 연결하는 최소 다리 길이를 파악하여 그래프 노드 만들기
void setBridge(int x, int y, int dir, vector<bool>& linked) {
	int myNum = land[x][y];
	int curX = x, curY = y;
	int nextX, nextY, linkLand, dist = 0;
	while (true) {
		nextX = curX + dx[dir];
		nextY = curY + dy[dir];
		if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) return;
		if (land[nextX][nextY] == myNum) return;
		dist++;
		if (land[nextX][nextY] != 0) { // 다른 섬을 만난 경우
			if (dist - 1 < 2) return;
			linkLand = land[nextX][nextY];
			linked[linkLand] = true;
			break;
		}
		curX = nextX;
		curY = nextY;
	}

	vector<int> ret(3);
	ret[0] = myNum;
	ret[1] = linkLand;
	ret[2] = dist-1;
	costs.push_back(ret);
	// printf("%d %d %d\n", ret[0], ret[1], ret[2]);
}

bool cmp(vector<int> v1, vector<int> v2) {
	return v1[2] < v2[2];
}

bool makeGraphNode() {
	vector<bool> linked(7, false);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (land[r][c] != 0) {
				for (int dir = 0; dir < 4; dir++) {
					setBridge(r, c, dir, linked);
				}
			}
		}
	}

	// 연결이 불가능한 섬이 있는지 확인
	for (int num = 1; num <= countIsland; num++) {
		if (linked[num] == false) return false;
	}

	// 비용이 적은 것부터 오름차순 정렬
	sort(costs.begin(), costs.end(), cmp);
	// printGraph();
	return true;
}

int getGroup(vector<int> group, int n) {
	if (group[n] == n) return n;
	else return getGroup(group, group[n]);
}

void printGroup(vector<int>& group) {
	for (int i = 1; i <= countIsland; i++) {
		printf("Island %d in group %d\n", i, getGroup(group, i));
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int ans = 0;

	scanf("%d %d", &N, &M);
	memset(land, 0, sizeof(land));
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &land[r][c]);
			if (land[r][c] == 1) land[r][c] = -1; // 땅인 부분은 -1로 표현
		}
	}

	setIsland();
	if (makeGraphNode() == false) {
		printf("-1\n");
		return 0;
	}
	
	// 최소신장트리(MST) 만들기
	vector<int> group(countIsland + 1, 0);
	for (int num = 1; num <= countIsland; num++) {
		group[num] = num;
	}
	int from, to, w;
	int groupA, groupB;
	for (int i = 0; i < costs.size(); i++) {
		from = costs[i][0];
		to = costs[i][1];
		w = costs[i][2];
		groupA = getGroup(group, from);
		groupB = getGroup(group, to);
		if (groupA == groupB) continue;
		ans += w;
		if (groupA < groupB) {
			group[groupB] = groupA;
		}
		else {
			group[groupA] = groupB;
		}
	}
	// printGroup(group);

	// 그래프가 하나에 속하지 않는 경우
	int ref = getGroup(group, 1);
	for (int i = 2; i <= countIsland; i++) {
		if (ref != getGroup(group, i)) {
			printf("-1\n");
			return 0;
		}
	}
	printf("%d\n", ans);
}