[백준] 1944번: 복제 로봇

📌 문제

https://www.acmicpc.net/problem/1944

📌 설명

처음에는 BFS만으로 문제를 해결하려고 했는데, 가능한 최대 복제 로봇 수를 알 수 없어서 문제를 풀 수 없었다. 이론 상 무한 개의 로봇이 복제될 수 있기 때문이다. 로봇이 무한히 복제될 수 있다는 의미를 다른 관점으로 바라보아야 한다.

출발지 ‘S’에서 시작하여, 모든 ‘K’를 줍고, 이때 로봇이 움직인 (최소)거리의 총합을 구해야 한다. 이 과정에서 로봇이 ‘S’ 또는 ‘K’에 위치하면 로봇은 복제가 가능하다. 즉, ‘S’ 또는 ‘K’ 지점을 로봇의 독립적인 출발지로 간주할 수 있다.

‘S’ 또는 ‘K’를 그래프의 노드로 바라보고, 각 노드를 연결하는 MST를 구해야 한다. 먼저 BFS를 통해 노드 간 최단 거리를 계산한 후, MST의 최소 거리를 구한다. 구현하기 나름이지만, 나는 MST의 총 노드의 수가 m + 1 이 아니면 -1을 출력하도록 하였다. 전체 노드의 수가 m + 1이기 때문이다.

📌 코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

char arr[51][51];
int visited[51][51];
vector<pair<int, int>> dist[252]; // i -> j 까지의 최단 거리 (i, j: nodes 벡터의 인덱스)
int n, m;
int mst[252];

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

int main() {
	// 1. BFS를 통해 S 또는 K 간 최단 거리를 구한다. -> 최단 거리를 구할 수 없는 지점이 존재하는 경우 -1
	// 2. S, K 간 MST의 최단 거리의 합을 구한다.

	cin >> n >> m;

	vector<pair<int, int>> nodes;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 'S' || arr[i][j] == 'K') {
				nodes.push_back({ i,j });
			}
		}
	}

	int dx[4] = { -1,0,1,0 };
	int dy[4] = { 0,1,0,-1 };

	queue<pair<int, int>> q;

	for (int i = 0; i < nodes.size(); i++) {
		// 각 노드에 대하여 BFS 수행
		memset(visited, -1, sizeof(visited));
		int x = nodes[i].first;
		int y = nodes[i].second;
		q.push({ x,y });
		visited[x][y] = 0;

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

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];

				if (!outOfBound(nx, ny) && arr[nx][ny] != '1' && visited[nx][ny] == -1) {
					visited[nx][ny] = visited[x][y] + 1;
					q.push({ nx,ny });
				}
			}
		}

		// 노드 간 최단 거리 초기화
		for (int j = 0; j < nodes.size(); j++) {
			if (i != j) {
				int x = nodes[j].first;
				int y = nodes[j].second;

				if (visited[x][y] != -1)
					dist[i].push_back({ j,visited[x][y] });
			}
		}
	}

	int total_dist = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	mst[0] = 1;
	int node_cnt = 1; // 현재 mst에 존재하는 노드의 수
	for (int i = 0; i < dist[0].size(); i++) {
		pq.push({ dist[0][i].second,dist[0][i].first });
	}

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

		if (mst[node]) continue;

		total_dist += d;
		node_cnt++;
		mst[node] = 1;

		for (int i = 0; i < dist[node].size(); i++) {
			int nnode = dist[node][i].first;
			int nd = dist[node][i].second;

			if (!mst[nnode]) {
				pq.push({ nd,nnode });
			}
		}
	}

	// 복제할 수 있는 위치는 m + 1개
	if (m + 1 != node_cnt)
		cout << -1;
	else
		cout << total_dist;
}

---

노드 간 BFS를 수행하여 최소 거리를 구하는 과정에서, 각 BFS의 시간복잡도는 $O(N^2)$이므로 총 $O(M\cdot N^2)$이다. MST를 계산하는 로직에서, 완전 그래프인 경우 간선의 수는 $O(M^2)$개이므로 전체 프림 알고리즘의 시간복잡도는 $O(M^2\cdot log(M))$이다. 최악의 경우 $N^2$이 $M\cdot log(M)$ 보다 크므로, 시간복잡도는 $O(M\cdot N^2)$에 수렴한다.

공간복잡도는 BFS의 큐에서 최악의 경우 모든 좌표가 들어가므로 $O(N^2)$, MST의 최단 거리를 저장하는 데 $O(M^2)$이므로 총 공간복잡도는 $O(N^2+M^2)$이다.