[Programmers] 지형 이동

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/62050

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

크루스칼 알고리즘을 이용한 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 사다리를 이용하지 않고 이동할 수 있는 지형들을 그룹핑해줍니다.

2. 그룹에서 다른 그룹으로 이동할 때 사용되는 사다리 비용을 구해주고 두 그룹과 함께 벡터에 넣어줍니다.

3. 2번에서 구한 벡터를 사다리 비용을 기준으로 오름차순 정렬을 해줍니다.

4. 크루스칼 알고리즘을 이용해 그룹을 합칠 때마다 사다리 비용을 결과에 더해줍니다.

5. 4번에서 구한 총비용을 반환해줍니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	const int MAX = 300;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	typedef struct
	{
	int groupA;
	int groupB;
	int cost;
	} Edge;
	bool cmp(Edge a, Edge b)
	{
	return a.cost < b.cost;
	}
	vector<int> parents;
	vector<Edge> edges;
	bool visited[MAX][MAX];
	int groups[MAX][MAX];
	int findParent(int u)
	{
	if (parents[u] == u)
	{
	return u;
	}
	return parents[u] = findParent(parents[u]);
	}
	int solution(vector<vector<int>> land, int height) {
	int group = 1;
	// 그룹핑
	for (int i = 0; i < land.size(); i++)
	{
	for (int j = 0; j < land.size(); j++)
	{
	if (visited[i][j])
	{
	continue;
	}
	queue<pair<int, int>> q;
	q.push({ i, j });
	visited[i][j] = true;
	groups[i][j] = group;
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= land.size() || nextX < 0 || nextX >= land.size())
	{
	continue;
	}
	if (visited[nextY][nextX] || abs(land[y][x] - land[nextY][nextX]) > height)
	{
	continue;
	}
	visited[nextY][nextX] = true;
	groups[nextY][nextX] = group;
	q.push({ nextY, nextX });
	}
	}
	group++;
	}
	}
	parents.resize(group);
	for (int i = 1; i < group; i++)
	{
	parents[i] = i;
	}
	// 그룹 간 거리 구함
	for (int y = 0; y < land.size(); y++)
	{
	for (int x = 0; x < land.size(); x++)
	{
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= land.size() || nextX < 0 || nextX >= land.size())
	{
	continue;
	}
	if (groups[y][x] == groups[nextY][nextX])
	{
	continue;
	}
	edges.push_back({ groups[y][x], groups[nextY][nextX], abs(land[y][x] - land[nextY][nextX]) });
	}
	}
	}
	sort(edges.begin(), edges.end(), cmp);
	int answer = 0;
	for (Edge edge : edges)
	{
	int groupA = findParent(edge.groupA);
	int groupB = findParent(edge.groupB);
	int cost = edge.cost;
	if (groupA == groupB)
	{
	continue;
	}
	parents[groupB] = groupA;
	answer += cost;
	}
	return answer;
	}
	int main(void)
	{
	vector<vector<int>> land = {
	{ 1, 4, 8, 10 },
	{ 5, 5, 5, 5 },
	{ 10, 10, 10, 10 },
	{ 10, 10, 10, 20 }
	};
	int height = 3;
	cout << solution(land, height) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~