[알고리즘] c++ cpp 지형 이동

포인트

1.  bfs, 프림 알고리즘을 섞는다. 
bfs 는 구역의 이름을 짓기위하여 실행을 한다 
프림은 mst 를 구하기 위하여 실행을 한다. 

2. 아직 이 문제는 어렵다. 억지로 풀기는 하였다
그래도 중요하다고 생각을 하는 부분은 중간에 있는 calc 함수라고 생각을 한다. 

calc 를 통해서 맵을 돌면서 인접 섹션이 다른 것들을 노드로 하고 이를 도는 mst 를 만드는 생각이 
중요한 것 같다. 
프림은 아무리 여러개가 연결이 되어 있어도 결국은 하나의 경로를 택하기 때문에 따로 처리는 상관이 없다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <queue>
#include <tuple>

using namespace std;

int section[301][301];
int visited[301][301];
int dist[1000010];

vector<pair<int, int>> vc[1000010];

int n, height, answer;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

// Prim Algorithm을 사용하였다.
void prim() {
	int start = 1;
	dist[start] = 1;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; //min heap 을 만들어준다.
	for (int i = 0; i < vc[start].size(); i++) {
		int x, cost;
		tie(x, cost) = vc[start][i];
		pq.push({cost, x});
	} // 집어 넣기

	while (!pq.empty()) {
		int cost, x;
		tie(cost, x) = pq.top();
		pq.pop();

		if (dist[x] == 1) continue;
		dist[x] = 1;
		answer += cost;

		for (int i = 0; i < vc[x].size(); i++) {
			int nx, ncost;
			tie(nx, ncost) = vc[x][i];
			pq.push({ncost, nx});
		}
	}
}


void calc(vector<vector<int>> map) {
	for (int i = 0; i < map.size(); i++) {
		for (int j = 0; j < map.size(); j++) {
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				// 한 구역에서 다른 구역으로 넘어가는 것 중에 섹션 간 이동인 한 쌍의 구역을 찾는다. 이 때, 탐색 지점이 맵 밖을 벗어나지 않게 한다.
				if (nx < 0 || nx >= map.size() || ny < 0 || ny >= map.size()) continue;
				if (section[i][j] != section[nx][ny]) {
					// 어차피 우선순위 큐에 의해서 한 쌍의 노드 간의 이동 통로 중 가장 작은 방법을 택해서 이동할 것이기 떼문에 갈 수 있는 방법을 그냥 다 저장해버리자.
					vc[section[nx][ny]].push_back({section[i][j], abs(map[i][j] - map[nx][ny])});
					vc[section[i][j]].push_back({section[nx][ny], abs(map[i][j] - map[nx][ny])});
				}
			}
		}
	}
	prim();
}


void bfs(vector<vector<int>> map, int height) {
	int secn = 0; // 모든 맵을 돌면서 사다리 없이 갈 수 있는 지역을 전부 같은 섹션으로 묶고, 방문 하지 않는 지점은 섹션으로 묶이지 않은 구역이므로 새로운 섹션으로 만들어준다.
	queue<pair<int, int>> q;
	for (int i = 0; i < map.size(); i++) {
		for (int j = 0; j < map.size(); j++) {
			if (visited[i][j] == 0) {
				secn++;
				section[i][j] = secn;
				visited[i][j] = 1;
				q.push({i, j});

				while (!q.empty()) {
					int x, y;
					tie(x, y) = q.front();
					q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx < 0 || nx >= map.size() || ny < 0 || ny >= map.size()) continue;
						if (!visited[nx][ny] && abs(map[x][y] - map[nx][ny]) <= height) {
							q.push({nx, ny});
							section[nx][ny] = secn; //같은 섹션으로 묶어 놓는다.
							visited[nx][ny] = 1;
						}
					}
				}
			}
		}
	}
	calc(map);
}


int solution(vector<vector<int>> land, int height) {
	bfs(land, height);
	return answer;
}