백준 - 다리 만들기2 (15898)

1. 문제 링크

문제 링크

2. 풀이

MST 알고리즘을 통해 푸는 문제입니다.
전체적인 단계는 다음과 같습니다.

1. BFS를 이용해 섬 나누기
2. 섬과 섬을 잇는 다리를 모두 구해서 인접리스트에 담기
3. 프림 알고리즘으로 최소 비용 구하기

3. 풀이

#define MAX 10
#include <bits/stdc++.h>

using namespace std;

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second > b.second;
	}
};

int n, m;
int land[MAX][MAX], visited[MAX][MAX];
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int d[7];
queue<pair<int, int>> q;
vector<pair<int, int>> adjList[7];
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

bool isOut(int y, int x) {
	return y < 0 || y >= n || x < 0 || x >= m;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> land[i][j];

	int area = 1;

	// 1. BFS를 이용해 영역 나누기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (land[i][j] != 1 || visited[i][j]) continue;

			q.push({ i, j });
			land[i][j] = area;
			visited[i][j] = 1;

			while (!q.empty()) {
				int y = q.front().first;
				int x = q.front().second;

				q.pop();

				for (int dir = 0; dir < 4; dir++) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (isOut(ny, nx)) continue;

					if (land[ny][nx] != 1) continue;

					if (visited[ny][nx]) continue;

					q.push({ ny, nx });
					land[ny][nx] = area;
					visited[ny][nx] = 1;
				}
			}

			area++;
		}
	}

	// 2. 섬과 섬을 잇는 다리를 모두 구해서 인접리스트에 담기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (land[i][j] == 0) continue;

			for (int dir = 0; dir < 4; dir++) {
				int len = 0;
				int y = i;
				int x = j;

				while (1) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (isOut(ny, nx)) break;

					// 본인 섬일 때
					if (land[ny][nx] == land[i][j]) break;

					// 다른 섬일 때
					if (land[ny][nx] > 0 && land[ny][nx] != land[i][j]) {
						// 길이가 2 이상일 때만 다리로 인정
						if (len >= 2) {
							adjList[land[i][j]].push_back({ land[ny][nx], len });
						}

						break;
					}

					y = ny;
					x = nx;
					len++;
				}
			}
		}
	}

	// 3. 프림 알고리즘으로 최소 비용 구하기
	int ans = 0;
	pq.push({ 1, 0 });

	// 다리는 n - 1 개만 있으므로 n - 1번 반복
	for (int i = 1; i < area; i++) {
		int nextNode = -1;
		int nextCost = -1;

		while (!pq.empty()) {
			int node = pq.top().first;
			int cost = pq.top().second;

			pq.pop();

			// 방문하지 않은 섬일 때, 
			if (!d[node]) {
				nextNode = node;
				nextCost = cost;
				break;
			}
		}

		// 이어진 섬이 없을 때
		if (nextNode == -1) {
			cout << -1;
			return 0;
		}

		// 비용 누적
		ans += nextCost;
		// 방문 표시
		d[nextNode] = 1;

		// 현재 섬과 이어진 다리 모두 넣기
		for (pair<int, int> edge : adjList[nextNode]) {
			pq.push(edge);
		}
	}

	cout << ans;

	return 0;
}

비슷한 문제로는 프로그래머스 - 지형 이동이 있습니다.