[백준 1944] 복제 로봇

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

1944번: 복제 로봇

요구사항

최소 이동거리로 열쇠를 get

 

풀이

1. 출발 위치와 열쇠 보관 위치 저장

2. 출발에서 열쇠까지 이동가는한지 확인

3. 출발+열쇠가 있는 지점에서 모든 다른 지점까지 거리 구하기(벡터 저장)

4. 정렬하기

5. Union-Find로 연결안되어 있다면 연결

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

struct go {
	int x;
	int y;
	int dist;
};
struct my {
	int x;
	int y;
};
int n, m;
char map[51][51];
int visit[51][51];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int parent[251];
vector<go> v;
bool com(go x, go y) {
	return x.dist < y.dist;
}

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

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y)
		return;
	else {
		parent[x] = y;
	}
}
int main() {
	queue<go> q;
	int cnt = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == 'S') {
				map[i][j] = 'K';
				q.push({ i,j });
				visit[i][j] = 1;
				v.push_back({ i,j });
			}
			else if (map[i][j] == 'K') {
				v.push_back({ i,j });
				cnt++;
			}
		}
	}
	
	while (!q.empty()) {
		int r = q.front().x;
		int c = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n)
				continue;
			if (visit[nr][nc] == 0) {
				if (map[nr][nc] == '0'){
					q.push({ nr,nc });
					visit[nr][nc] = 1;
				}
				if (map[nr][nc] == 'K') {
					q.push({ nr,nc });
					visit[nr][nc] = 1;
					cnt--;
				}
			}
			

		}
	}
	if (cnt != 0) {
		cout << "-1" << endl;
		return 0;
	}
	vector<go> ans;
	for (int i = 0; i < v.size(); i++) {
		int r = v.at(i).x;
		int c = v.at(i).y;
		for (int j = i + 1; j < v.size(); j++){
			int nr = v.at(j).x;
			int nc = v.at(j).y;
			int dist = 0;
			memset(visit, 0, sizeof(visit));
			queue<go> qq;
			qq.push({ r,c ,0});
			visit[r][c] = 1;
		//	cout << "!@#!@1341234312" << endl;
			//cout << "nr" << nr << "nc" << nc << endl;
			while (!qq.empty()) {
				int nowr = qq.front().x;
				int nowc = qq.front().y;
				int nowdist = qq.front().dist;
				//cout << "my" << endl;
			//	cout << nowr << " " << nowc << endl;
			//	cout << nr << " " << nc << endl;
				if (nowr == nr && nowc == nc) {
				//	cout << "!" << endl;
					dist = nowdist;
					break;
				}
				qq.pop();
				for (int i = 0; i < 4; i++) {
					int nextr = nowr + dr[i];
					int nextc = nowc + dc[i];
					int nextdist = nowdist + 1;
					if (nextr < 0 || nextc < 0 || nextr >= n || nextc >= n)
						continue;
					if (visit[nextr][nextc] == 1)
						continue;
					if (visit[nextr][nextc] == 0) {
						if (map[nextr][nextc] == '0') {
						//	cout << "!@#" << endl;
							qq.push({ nextr,nextc,nextdist });
							visit[nextr][nextc] = 1;
						}
						if (map[nextr][nextc] == 'K') {
						//	cout << "!@1111#" << endl;
						//	cout << nextr << " " << nextc << endl;
							qq.push({ nextr,nextc ,nextdist});
							visit[nextr][nextc] = 1;
						}
					}
				
				}
			}
			ans.push_back({ i,j,dist });
		}
	}
	//cout << "anssize" << ans.size() << endl;
	sort(ans.begin(), ans.end(), com);
	for (int i = 1; i <= 250; i++) {
		parent[i] = i;
	}
	int tans = 0;
	for (int i = 0; i < ans.size(); i++) {
		int x = ans.at(i).x;
		int y = ans.at(i).y;
		int dist = ans.at(i).dist;
		//cout << x << " " << y << " " << dist << endl;
		if (Find(x) != Find(y)) {
			Union(x, y);
			//cout << "As" << ans.at(i).dist << endl;
			tans += ans.at(i).dist;
			//cout << "A" << endl;
		}
	}
	cout << tans << endl;

	
}