[BOJ]백준 1944번: 복제 로봇(C++) / MST, BFS

www.acmicpc.net/problem/1944

1944번: 복제 로봇

스터디 문제 풀이용으로 급하게 서치한 문제인데 굉장히 유익한 것 같아서 포스팅

로봇의 시작 좌표 S가 주어지고, 열쇠의 좌표 K(여러 개)가 주어졌을 떄 모든 열쇠를 얻을 수 있는 최단거리 이동 경로를 구해야 한다.

이 때, 이동 경로에는 가중치가 없고(BFS를 이용한 최단거리 계산) 열쇠가 복사가 가능하기 때문(S에서만 K를 도달할 수 있는게 아닌, K에서 다른 K로도 이동 가능)에 MST로 풀이가 가능하다.

즉 이런 식으로 S, K들 사이에 edge를 연결(좌표 상에서의 최단거리 계산으로)해서 거리를 구하고, 그 edge들의 cost합이 최소가 되는 MST를 생성하면 된다.

나는 그림에 적은 것 처럼 모든 좌표에서 BFS를 돌려서 좌표 상에서의 최단 거리를 구해주고, 그것을 이용해서 MST를 만들었다. cost값이 하나라도 INF인 노드가 있다면 MST를 생성할 수 없다는 뜻 이므로(MST는 connected graph에서만 생성 가능) -1를 return해주었다.

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#define INF 987654321
#define pii pair<int,int>
using namespace std;

typedef struct { int x,y; }point;
//string map[51];
int map[51][51];
int n, m,dist[255][255];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
vector<point> v;

void bfs(point p) {
	bool visit[51][51] = { 0 };
	queue<point> q;

	q.push({ p.x,p.y });
	visit[p.y][p.x] = 1;
	
	int d = 0;
	while (!q.empty()) {
		int size = q.size();
		for (int s = 0; s < size; s++) {
			point cur = q.front(); q.pop();
			if (map[cur.y][cur.x] > 0) {
				dist[map[p.y][p.x]][map[cur.y][cur.x]] = d;
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i], ny = cur.y + dy[i];
				if (map[ny][nx] == -1 || visit[ny][nx])continue;
				q.push({ nx,ny });
				visit[ny][nx] = 1;
			}
		}
		d++;
	}
}

int prim() {
	priority_queue<pii, vector<pii>, greater<>> pq;
	vector<int> cost(m + 2, INF);
	vector<int> prev(m + 2, -1);
	vector<bool> visit(m + 2, false);

	int ans = 0;
	pq.push(make_pair(0, 1));
	cost[1] = 0;

	while (!pq.empty()) {
		pii cur = pq.top(); pq.pop();
		if (visit[cur.second])continue;

		visit[cur.second] = 1;
		for (int i = 1; i <= m + 1; i++) {
			if (dist[cur.second][i] != INF &&
				(cost[i] > dist[cur.second][i])
				&&!visit[i]) {
				cost[i] = dist[cur.second][i];
				prev[i] = cur.second;
				pq.push(make_pair(cost[i], i));
			}
		}
	}

	for (int i = 1; i <= m + 1; i++) {
		if (cost[i] == INF)return -1;
		ans += cost[i];
	}

	return ans;
}

int main() {
	cin >> n >> m;
	int eNum = 2;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			switch (s[j]) {
			case '1':
				map[i][j] = -1;
				break;
			case '0':
				map[i][j] = 0;
				break;
			case 'S':
				map[i][j] = 1;
				v.push_back({ j,i });
				break;
			default:
				map[i][j] = eNum++;
				v.push_back({ j,i });
				break;
			}
		}
	}

	fill(&dist[0][0], &dist[m + 3][m + 2], INF);
	for (int i = 0; i < v.size(); i++)
		bfs(v[i]);

	printf("%d", prim());
	return 0;
}

너무 빤한 MST 문제가 아닌 고민할 거리를 추가해줘서 good problem이라고 생각한다.