지형 이동 C++

https://programmers.co.kr/learn/courses/30/lessons/62050

코딩테스트 연습 - 지형 이동

#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAX = 305;
struct MOVE { int x, y; };
MOVE mv[4] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int r, c, h;
int answer = 0;
int map[MAX][MAX];
int group = 0;
struct INFO { int cost, start, end; };
vector<INFO> v;
vector<int> parent;
vector<vector<int>> land_tmp;

void dfs(int ii, int jj) {
	map[ii][jj] = group;

	for (int k = 0; k < 4; k++) {
		int movei = ii + mv[k].x;
		int movej = jj + mv[k].y;

		if (!(movei >= 0 && movei < r && movej >= 0 && movej < c)) continue;
		else if (map[movei][movej] != -1) continue;

		int diff = abs(land_tmp[ii][jj] - land_tmp[movei][movej]);
		if (diff > h) {
			continue;
		}

		else {
			map[movei][movej] = group;
			dfs(movei, movej);
		}
	}
}

int getParent(int i) {
	if (parent[i] == i) return i;
	else return getParent(parent[i]);
}

void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a > b) parent[a] = b;
	else parent[b] = a;
}

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

int solution(vector<vector<int>> land, int height) {
	r = land.size();
	c = land[0].size();
	h = height;
	land_tmp = land;

	memset(map, -1, sizeof(map));

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] == -1) {
				dfs(i, j);
				group++;
			}
		}
	}

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {

			for (int k = 0; k < 4; k++) {
				int movei = i + mv[k].x;
				int movej = j + mv[k].y;

				if (!(movei >= 0 && movei < r && movej >= 0 && movej < c)) continue;
				if (map[movei][movej] == map[i][j]) continue;

				v.push_back({ abs(land_tmp[movei][movej] - land_tmp[i][j]),map[movei][movej],map[i][j] });
			}
		}
	}

	sort(v.begin(), v.end(), cmp);
	parent.resize(group + 1);

	for (int i = 0; i <= group; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < v.size(); i++) {
		if (getParent(v[i].start) != getParent(v[i].end)) {
			answer += v[i].cost;
			unionParent(v[i].start, v[i].end);
		}
	}
	return answer;
}