백준 1944 - 복제 로봇(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1944

1944번: 복제 로봇

BFS와 MST를 이용해 푸는 문제입니다.

저는 이 문제를 한 구역에서 다른 구역까지의 거리 최솟값을 저장한 뒤, Union-Find를 이용해 구했습니다.

로봇은 언제 생성하든 시간이 들지 않기에, MST를 통해 최솟값을 구하면 자연스럽게 풀리는 문제입니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321

using namespace std;

int N, M;
int Node = 1;
char map[51][51];
int go_through[51][51], check[51][51];
pair<int, int> start;
vector<pair<int, int>> key;
int key_way[256];
int dx[4] = { 1,0,-1,0};
int dy[4] = { 0,1,0,-1};
typedef struct con {
	int x;
	int y;
	int cost;
}con;
vector<con> line;
bool cant = true;

void bfs(pair<int,int> X, int Y_x, int Y_y, int Node_1, int Node_2) {
	bool check_key[51][51];
	memset(check_key, false, sizeof(check_key));
	queue<pair<pair<int, int>, int>> q;
	check_key[X.first][X.second] = true;
	q.push({ {X.first, X.second},0 });
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cost = q.front().second;
		q.pop();
		if (x == Y_x && y == Y_y) {
			line.push_back({ Node_1, Node_2, cost });
			return;
		}
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (map[xx][yy] != '1' && !check_key[xx][yy]) {
					check_key[xx][yy] = true;
					q.push({ {xx, yy},cost + 1 });
				}
			}
		}
	}
	cant = false;
}

void get_distance() {
	for (int i = 0; i < key.size(); i++) {
		int x = key[i].first;
		int y = key[i].second;
		bfs(start, x, y, 0, check[x][y]);
		if (cant == false) {
			cout << "-1";
			return;
		}
	}
	for (int i = 0; i < key.size(); i++) {
		for (int j = i + 1; j < key.size(); j++) {
			bfs(key[i], key[j].first, key[j].second, check[key[i].first][key[i].second], check[key[j].first][key[j].second]);
			if (cant == false) {
				cout << "-1";
				return;
			}
		}
	}
}

bool cmp(con a, con b) {
	if (a.cost < b.cost) return true;
	else return false;
}

int Find(int x) {
	if (key_way[x] == x) return x;
	else return key_way[x] = Find(key_way[x]);
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	key_way[x] = y;
}

void solve() {
	int min_cost = 0;
	get_distance();
	if (!cant) return;
	for (int i = 0; i < Node; i++) key_way[i] = i;
	sort(line.begin(), line.end(), cmp);
	for (int i = 0; i < line.size(); i++) {
		int x = Find(line[i].x);
		int y = Find(line[i].y);
		if (x != y) {
			Union(x, y);
			min_cost += line[i].cost;
		}
	}
	cout << min_cost;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'S') start = { i,j };
			else if (map[i][j] == 'K') {
				key.push_back({ i,j });
				check[i][j] = Node++;
			}
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요