백준 No.1944 [복제 로봇]

백준 No.1944 [복제 로봇]

---

  문제 

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

1944번: 복제 로봇

---

  설명 

 <알고리즘 분류> 
 * MST
 * BFS

 

  위와 같은 테스트 케이스가 있다고 하자!

 

  먼저, bfs 를 통해 위와 같이 하나의 시작점과 각 Key 들이 이루는 그래프를 구했다.

  그래프의 간선들은, 연결된 두 노드의 최소 거리이다.

 

  Key는 최대 250개, 지도 크기는 최대 50 * 50 == 2,500 이니까, Key 하나하나 2,500 크기의 맵을 BFS 해도

최대 250 * 2,500 == 625,000 번 탐색되므로,TLE나 메모리 초과는 없다!

  

  이제, 위 그래프를 토대로 MST 를 진행한다. 이 때 조건이 있다.

 

 

 

 조건 #1 

  시작점에서는 한 개의 로봇만이 출발한다. 즉, 시작 노드와 연결된 간선은 한 개 밖에 없다.

 

 

 

 조건 #2

  각 Key 가 있는 노드에는 로봇 한 개가 방문하면, 로봇이 복제되어 최대 두 개의 로봇이 다른 Key 를 찾아 떠날 수 있다.

즉, 각 Key 가 있는 노드와 연결되는 간선은 최대 3개 이다.

 

  위 두 조건으로 MST 를 구현하면서 그 MST 의 간선들의 가중치의 합을 구하면 정답이 된다. 그런데 만약, 한 개의 Key 라도 벽에 막혀서 집을 수 없다면 가중치의 합이 inf 보다 큰 수를 나타내도록 구현하였다. 가중치의 합이 inf 미만이라면, 가중치의 합을 출력하고 그렇지 않다면 -1 을 출력하게끔 하였다.

 

 <정리> 
1. 각 key 들 끼리의 거리를 구한다.
2. 위 거리들을 구하면서, key 들로 이루어진 그래프가 형성되었다.
3. 이 그래프에서 MST 를 구한다.
   - 단, 조건은 시작 Node 에 연결된 간선은 하나, Key 가 있는 Node 들에 연결된 간선은 최대 3개 이다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>

#define inf 99'999
#define N 51	// arr's max size
#define M 251	// key's max count

using namespace std;

struct pos {
	int r, c;
	int val;
};

struct pos2 {
	char val;
	int idx;
};

struct comp {
	bool operator()(pos& a, pos& b) {
		return a.val > b.val;
	}
};

pos2 arr[N][N];		// 지도
int robot[N][N];	// robot[r][c] == (r, c) 위치에서 연결된 간선 개수
int key_find = 0;	// 찾은 key 개수
int n, k;

vector<pos> keys;	// key 들의 위치를 담은 vector array
int key_dist[M][M];	// key_dist[a][b] == keys array 에서 a, b 번째 key 간 거리
pos start;			// 시작 위치

int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

inline bool isSafe(const int& r, const int& c) {
	return 1 <= r && r <= n && 1 <= c && c <= n;
}

void bfs(const int& sr, const int& sc) {
	bool visit[N][N] = { false, };
	queue<pos> q;
	q.push(pos{ sr, sc, 0 });
	visit[sr][sc] = 0;

	while (!q.empty()) {
		pos cur = q.front(); q.pop();

		if (arr[cur.r][cur.c].idx != -1)
			key_dist[arr[cur.r][cur.c].idx][arr[sr][sc].idx]
				= key_dist[arr[sr][sc].idx][arr[cur.r][cur.c].idx]
				= min(key_dist[arr[cur.r][cur.c].idx][arr[sr][sc].idx], cur.val);

		for (int d = 0; d < 4; d++) {
			int nr = cur.r + dr[d];
			int nc = cur.c + dc[d];

			if (isSafe(nr, nc) && !visit[nr][nc] && arr[nr][nc].val != '1') {
				q.push({ nr, nc, cur.val + 1 });
				visit[nr][nc] = true;
			}
		}
	}
}

void setDist() {	// 50 * 50 map 에서 250 번 bfs ? 가능할듯
	for (int i = 0; i < keys.size(); i++)
		for (int j = 0; j < keys.size(); j++)
			if (i != j) key_dist[i][j] = inf;

	for (int i = 0; i < keys.size(); i++)
		bfs(keys[i].r, keys[i].c);
}

int mst() {
	bool visit[M] = { false, };
	priority_queue<pos, vector<pos>, comp> pq;
	int ret = 0;
	
	int start_idx = keys.size() - 1;	// index of start point
	for (int i = 0; i < keys.size() - 1; i++)	// keys 의 마지막이 sp 이므로 빼고 go
		pq.push({ keys[i].r, keys[i].c, key_dist[i][k] });
	visit[k] = true;

	while (!pq.empty()) {
		pos cur = pq.top(); pq.pop();

		if (visit[arr[cur.r][cur.c].idx]) continue;

		robot[cur.r][cur.c]++;	// 시작점이 되는 key를 pick!
		visit[arr[cur.r][cur.c].idx] = true;
		key_find++;
		ret += cur.val;

		if (key_find == k) return (ret < inf? ret : -1);
		if (robot[cur.r][cur.c] == 3) continue; // 더이상 뻗을 수 없으므로.

		robot[cur.r][cur.c]++;	// cur node 에서 뻗어 나가므로 또 추가!
		for (int i = 0; i < keys.size(); i++) {
			if (visit[arr[keys[i].r][keys[i].c].idx]) continue;
			pq.push({ keys[i].r, keys[i].c
				, key_dist[arr[cur.r][cur.c].idx][arr[keys[i].r][keys[i].c].idx] });
		}
	}

	return -1;
}

int solve() {
	setDist();	// key 간 dist setting=
	return mst();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;

	string row;
	for (int i = 1; i <= n; i++) {
		cin >> row;
		for (int j = 1; j <= n; j++) {
			arr[i][j] = { row[j - 1], -1 };
			if (arr[i][j].val == 'S') {
				start = pos{ i, j, 0 };
				arr[i][j].val = '0';
			}
			else if (arr[i][j].val == 'K') {
				keys.push_back(pos{ i, j, 0 });
				arr[i][j].idx = keys.size() - 1;
			}
		}
	}

	keys.push_back({ start.r, start.c, 0 });
	arr[start.r][start.c].idx = keys.size() - 1;

	cout << solve() << '\n';
}