[백준 1944] 복제 로봇

문제 링크 : 1944번: 복제 로봇 (acmicpc.net)

1944번: 복제 로봇

 

최소 스패닝 트리 문제이다.

문제의 input 을 고려해서 어떻게 정답을 찾을지를 생각해보도록 하자.

 

5 2
11111
1S001
10001
1K1K1
11111

 

우선, 문제에서 요구한 것은 로봇의 시작지점인 S 부터 열쇠 K 를 모두 획득하는데 움직이는 횟수의 합을 최소로 하는 것이다.

(2, 2) 에 있는 S 로 부터 시작하여 (2, 2) => (4, 2) => (4, 4) 으로 총 6 만큼 이동하거나 또는 (2, 2) => (4, 4) => (4, 2) 으로 총 6 만큼 이동할 수 있다.

 

그렇다면 자연스럽게 각 지점마다 한번씩 방문하면서 최소로 움직이도록 하려면 어떻게 해야할까?

 

최소 스패닝 트리를 이용하여 해결할 수 있다.

S, K 지점을 전부 connection 하여 해당 간선들의 정보를 이용하여 크루스칼 알고리즘을 활용하면 된다.

 

 

문제 접근 순서

 

① 우선 (1, 1) 부터 (N, N) 까지 차례로 탐색하면서 'S' 또는 'K' 인 지점을 발견할 때 마다 connection 이 이뤄지도록 한다.

시작 정점 (start_x, start_y) 으로 미로를 bfs 방식으로 또 다른 정점 'S' 또는 'K' 를 발견하게 되면 시작 정점으로부터 얼마나 이동했는지에 대한 정보를 벡터에다가 넣어줬다. 

이때, 정점을 하나의 값으로 압축시켜서 {시작 정점, 발견된 정점, 거리} 를 벡터에다가 넣어줬는데 그 이유는 union find 를 사용하기 위함이다.

시간 복잡도는 모든 정점들이(O(\(M\))) connection (O(\(N^{2}\)))하므로 O(\(MN^{2}\)) 이다.

 

② 연결된 정점들을 가지고 최소 스패닝 트리를 구하면 된다.

우선 {시작 정점, 발견된 정점, 거리} 에 대한 정보를 담은 벡터를 거리 순으로 오름차순으로 정렬을 시킨다.

그리고 union find 를 통해 두 정점이 동일한 parent 를 갖지 않을 경우 connection 을 해주면서 parent 를 업데이트 한다.

즉, 이러한 operation 을 하는데 시간 복잡도는 O(\(Nlog(N) + N\)) = O(\(Nlog(N)\)) 이다.

 

③ 스패닝 트리의 가중치를 출력하면 된다.

여기서 하나 놓쳤던 점은 connection 이 총 M 개인지를 판단해야 한다. (M 은 K 의 갯수)

즉, 완벽하게 트리가 형성되어야만 시작 지점의 로봇이 모든 열쇠를 획득한 경우이며 그렇지 않은 경우는 열쇠를 전부 획득하지 못한 경우이다.

따라서 총 M 개만큼 connection 이 되면 가중치를 출력하고 그렇지 않은 경우 -1 을 출력하면 된다.

 

문제 풀이 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
char Map[51][51];
int parent[2501];
bool visited[51][51];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void input() {
	string s;

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> s;
		for (int j = 1; j <= N; j++) {
			Map[i][j] = s[j - 1];
		}
	}
}

int get_parent(int x, int parent[]) {
	if (x == parent[x])
		return x;
	return (parent[x] = get_parent(parent[x], parent));
}

void go_union(int x, int y, int parent[]) {
	x = get_parent(x, parent);
	y = get_parent(y, parent);
	if (x > y) parent[x] = y;
	else parent[y] = x;
}

bool compare(pair<pair<int, int>, int> x, pair<pair<int, int>, int> y) {
	return x.second < y.second;
}

int trans(int x, int y) {
	return (x - 1) * N + y;
}

void init_visited(bool visited[][51]) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			visited[i][j] = false;
		}
	}
}

void bfs(int start_x, int start_y, vector<pair<pair<int, int>, int>>& info) {
	queue<pair<pair<int, int>, int>> Q;

	init_visited(visited);
	Q.push({ { start_x, start_y }, 0 });
	visited[start_x][start_y] = true;
	while (!Q.empty()) {
		int x = Q.front().first.first, y = Q.front().first.second;
		int dist = Q.front().second;
		Q.pop();

		if (!(start_x == x && start_y == y) && (Map[x][y] == 'S' || Map[x][y] == 'K')) {
			info.push_back({ {trans(start_x,start_y), trans(x,y)}, dist });
		}
		for (int i = 0; i < 4; i++) {
			int next_x = x + dx[i], next_y = y + dy[i];
			if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
				if (!visited[next_x][next_y] && Map[next_x][next_y] != '1') {
					visited[next_x][next_y] = true;
					Q.push({ { next_x,next_y }, dist + 1 });
				}
			}
		}
	}
}

void set_path(vector<pair<pair<int, int>, int>> &info) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Map[i][j] == 'S' || Map[i][j] == 'K') {
				bfs(i, j, info);
			}
		}
	}

	sort(info.begin(), info.end(), compare);
}

void solution() {
	vector<pair<pair<int, int>, int>> info;
	int connected = 0, result = 0;
	
	for (int i = 1; i <= N * N; i++) {
		parent[i] = i;
	}
	set_path(info);
	for (int i = 0; i < info.size(); i++) {
		int x = info[i].first.first, y = info[i].first.second;
		int c = info[i].second;

		if (get_parent(x, parent) != get_parent(y, parent)) {
			go_union(x, y, parent);
			connected++;
			result += c;
		}
	}
	if (connected == M) cout << result;
	else cout << -1;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();

	return 0;
}