알고리즘/BOJ

[BOJ / 1994 / C++] 복제 로봇

나태준 2021. 9. 27. 03:18
반응형

오랜만의 글...

 

어느정도 알고리즘 공부도 적응 된 것 같아서 괜찮은 것 같은 코드는 올려보려고한다.

 

포스팅은 나중에 제대로 하도록 하고 간단한 설명과 코드만 일단...

 

이 문제는 아이디어적으로 크게 어려운건 아니고 BFS와 MST를 조합하는 문제다.

 

개인적인 생각으로 코테에서 적당한 수준으로 문제를 낸다면 이정도 난이도가 아닐까 싶다.

 

1. 맵 크기와 키 개수, 맵을 문자열로 입력받는다.

2. BFS로 먼저 시작점부터 각 키까지의 거리, 또 각 키간의 거리를 측정해 그래프화한다.

> 제일 기본적인 "queue를 이용한 BFS"를 해주면 된다. 단, 키 부분에 도달시 로봇을 복제를 해줘야 한다.

> 이 문제는 MST를 활용하면서 스토리를 더한 문제이지 기본적인 문제이기 때문에 무조건 키에 처음 도달시 한번만 한개의 로봇을 복제해주면 된다.

> 문제에 장황하게 쓰여있는건 MST를 쓰게하기 위한 전제 조건일 뿐이다 (이동에 횟수를 안먹고 시간 제한이 없고... 어쩌고 저쩌고...)

3. 크루스칼 알고리즘을 통해 MST 탐색을 수행한다.

> 우선순위 큐(최소 힙)와 Union-Find만 쓰면 되는 기본 문제. N과 M이 크지도 않으므로 메모리 제한도 상관이 없다.

 

* 개인적으로 신경쓰이는 부분은 아직 C++이 익숙치 않아서인지 pq사용시 호출연산자 오버로딩이 잘 이해가 안된다.

 

 

더보기
#include <iostream>
#include <queue>
using namespace std;

#define S 0

struct Node {
	int start;
	pair<int, int> pos;
	int distance;
};

char map[50][50];
int visited[251][50][50];
int key[50][50];
int group[251];
int groupCnt[251];

struct comp {
	int operator()(pair<pair<int, int>, int> I, pair<pair<int, int>, int> C)
	{
		if (I.second != C.second) return I.second > C.second;
		if (I.first.first != C.first.first) return I.first.first > C.first.first;
		return I.first.second > C.first.second;
	}
};

int findBoss(int x)
{
	return (x == group[x]) ? x : findBoss(group[x]);
}

int setUnion(int x, int y)
{
	int xBoss = findBoss(x);
	int yBoss = findBoss(y);
	if (xBoss == yBoss) return 0;
	group[yBoss] = xBoss;
	groupCnt[xBoss] += groupCnt[yBoss];
	groupCnt[yBoss] = 0;
	return 1;
}

int main() {
	int N, M, K = 1;
	int flag = 0;
	int result = 0;

	queue<Node> q;
	priority_queue< pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, comp> pq;

	cin >> N >> M;
	for (int y = 0; y < N; y++)
	{
		cin >> map[y];

		for (int x = 0; x < N; x++)
		{
			if (map[y][x] == 'S')
			{
				group[S] = S;
				groupCnt[S] = 1;

				q.push({ S, {y,x}, 0 });
				visited[S][y][x] = true;
			}
			else if (map[y][x] == 'K')
			{
				group[K] = K;
				groupCnt[K] = 1;
				key[y][x] = K++;
			}
		}
	}

	while (!q.empty())
	{
		int y = q.front().pos.first;
		int x = q.front().pos.second;
		int d = q.front().distance;
		int s = q.front().start;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			const int dy[] = { 1, -1, 0, 0 };
			const int dx[] = { 0, 0, -1, 1 };
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny > N - 1 || nx > N - 1) continue;
			if (map[ny][nx] == '1') continue;
			if (visited[s][ny][nx]) continue;
			visited[s][ny][nx] = 1;
			q.push({ s, {ny, nx}, d + 1 });

			if (map[ny][nx] == 'K')
			{
				visited[key[ny][nx]][ny][nx] = 1;
				q.push({ key[ny][nx], {ny, nx}, 0 });
				pq.push({ { s, key[ny][nx] }, d + 1 });
			}
		}
	}

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

		if (setUnion(s, e))
		{
			result += d;
			if (flag |= (groupCnt[findBoss(s)] == K)) break;
		}
	}

	cout << (flag ? result : -1);

	return 0;
}

 

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ / 16234 / C++] 인구 이동  (0) 2021.09.27
[BOJ / 1994 / C++] 복제 로봇  (0) 2021.09.27
1 2
자바스크립트를 활성화시켜주세요!
[활성화]