프로그래머스 Level 4 지형이동

지형이동 (프로그래머스 Level 4)

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

전형적인 탐색 문제인 줄 알고 BFS(유사 다익스트라)를 이용하여 풀었으나,
이후 2번째 예제에서 ‘서로 다른 지역’에 따른 사다리 비용을 구해야 한다는 점에서
갑자기 불길한 예감이 들었다

결국 다익스트라로는 해당 부분을 풀어낼 수 없었고,
해당 부분에서 유니온 파인드의 구현이 필요할 거라 생각한 점에서
최소신장트리(MST) 문제임은 짐작할 수 있었으나
해당 부분에 대한 구현을 떠올릴 수 없었기에 결국 검색하여 코드를 이해하였다

흥미로운 점은 ‘rank’를 이용하여
‘rank가 낮은’ 트리를 ‘rank가 높은’ 트리에 편입시키는
방식으로 시간 복잡도를 개선하는 방식이였다

• 특정 트리의 ‘부모’ 노드를 자기 자신이 아닌
  상위 트리를 가리키게 됨으로서, 다음 find 함수 호출 시
  해당 하위 트리의 노드들의 부모도 재귀 호출을 통해 바뀌게 된다
  

또한 ‘맵’의 각 부분을 node와 edge로 해석한다는 부분이
인상깊었는데, 다양한 문제를 그래프와 연관지을 수 있다는 점을 다시 실감한 것 같다

Code

#include <vector>
#include <queue>
#include <limits.h>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

const int dirCount = 4;
const int dy[] = { 1, 0, -1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int find(vector<int>& parent, int x)
{
	// 자기 자신이 부모가 아니라면 부모를 찾는다
	if (parent[x] != x) 
	{
		parent[x] = find(parent, parent[x]);
	}
	return parent[x];
}

void unite(vector<int>& parent, vector<int>& rank, int x, int y) 
{
	// 두 '뭉치'를 결합시켜준다
	int rootX = find(parent, x);
	int rootY = find(parent, y);

	if (rootX != rootY)
	{
		// rank가 높은 트리에 rank 낮은 트리를 병합시킨다
		// 이후 나머지 녀석들은 find를 호출시키면 다시 root를 찾아가며 바뀌게 됨
		if (rank[rootX] > rank[rootY])
		{
			parent[rootY] = rootX;
		}
		else if (rank[rootX] < rank[rootY])
		{
			parent[rootX] = rootY;
		}
		else
		{
			parent[rootY] = rootX;
			rank[rootX]++;
		}
	}
}

int solution(vector<vector<int>> land, int height) {
	// 전형적인 탐색 문제인줄 알았는데
	// 실상은 그래프 문제이며, 그 중에서도 mst와 관련된 문제...

	struct Edge {
		int cost;
		int x1, y1, x2, y2;
		bool operator<(const Edge& other) const
		{
			return cost < other.cost;
		}
	};

	const int n = land.size();
	vector<Edge> edges;

	// land 돌면서 '간선' 만들기
	for (int x = 0; x < n; ++x)
	{
		for (int y = 0; y < n; ++y)
		{
			for (int i = 0; i < dirCount; ++i)
			{
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n)
					continue;

				int cost = abs(land[x][y] - land[nx][ny]);
				if (cost > height)
				{
					edges.push_back({ cost, x, y, nx, ny });
				}
				else
				{
					edges.push_back({ 0, x, y, nx, ny });
				}
			}
		}
	}

	sort(edges.begin(), edges.end());

	// 1차원으로
	vector<int> parent(n * n);
	vector<int> rank(n * n, 0);

	// 처음엔 자기 자신을 부모로 설정 
	for (int i = 0; i < n * n; ++i)
	{
		parent[i] = i;
	}

	int answer = 0;
	for (const auto& edge : edges)
	{
		// 각 edge를 parent쪽의 1차원으로 변경
		int x1 = edge.x1 * n + edge.y1;
		int x2 = edge.x2 * n + edge.y2;

		// 두 edge의 부모가 다르다면
		// 하나로 합치고 answer를 그 cost 만큼 증가시켜준다
		if (find(parent, x1) != find(parent, x2))
		{
			unite(parent, rank, x1, x2);
			answer += edge.cost;
		}
	}

	return answer;
}