[윈터코딩] 지형이동

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

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

요즘은 dfs, bfs 단독으로 문제가 나오기 보다는 그래프 탐색을 이용하혀 한번 더 알고리즘 개념을 이용한 문제들이 종종 있는것을 볼 수 있다.

이번에는 그래프 탐색과 MST(최소비용 신장 트리) 개념을 합친 문제를 풀어 보았다.

나중에 프림스 알고리즘과 크루스칼 알고리즘에 대하여도 정리를 하여 포스팅을 하여 정리 할 필요를 느꼈다.

 

1, bfs를 이용하여 그룹을 지어준다

 

2, 그룹간 사다리를 놓을 수 있는 모든 경우의 수를 벡터에 저장한다.

 

3, 사다리 길이가 짧은 순으로 정렬을 한 다음 크루스칼 알고리즘을 이용하여 연결을 시켜준다.

- 크루스칼 알고리즘의 핵심은 짧은 간선을 선택하고 싸이클이 발생하지 않으면 간선을 연결(union find 알고리즘 사용)

 

소스코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int group_num = 1;
int visited[301][301];
int dr[] = { 1,0,-1,0 };
int dc[] = { 0,1,0,-1 };
vector<int> parent;
vector<pair<int, pair<int, int>>> edge;
queue<pair<int, int>> q;


int get_parent(int search) {
	if (parent[search] == search) return search;

	return parent[search] = get_parent(parent[search]);
}

void union_parent(int a, int b) {
	int a_parent = get_parent(a);
	int b_parent = get_parent(b);

	parent[a_parent] = b_parent;
}

int solution(vector<vector<int>> land, int height) {
	int answer = 0;

	int row_size = land.size();
	int col_size = land.size();

	//그룹을 지어줌
	for (int i = 0; i < row_size; i++) {
		for (int j = 0; j < col_size; j++) {
			if (visited[i][j] == 0) {
				group_num++;
				q.push(make_pair(i, j));
				visited[i][j] = group_num;
			}

			while (!q.empty()) {
				int r = q.front().first;
				int c = q.front().second;
				q.pop();

				for (int k = 0; k < 4; k++) {
					int nr = r + dr[k];
					int nc = c + dc[k];

					if (nr < 0 || nr >= row_size || nc < 0 || nc >= col_size) continue;

					if (visited[nr][nc] == 0 && abs(land[r][c] - land[nr][nc]) <= height) {
						visited[nr][nc] = group_num;
						q.push(make_pair(nr, nc));
					}
				}
			}

		}
	}

	//그룹의 연결 정보를 저장
	for (int i = 0; i < row_size; i++) {
		for (int j = 0; j < col_size; j++) {
			for (int k = 0; k < 4; k++) {
				int nr = i + dr[k];
				int nc = j + dc[k];

				if (nr < 0 || nr >= row_size || nc < 0 || nc >= col_size) continue;
				
				if (visited[i][j] != visited[nr][nc]) {
					edge.push_back(make_pair(abs(land[i][j] - land[nr][nc]), make_pair(visited[i][j], visited[nr][nc])));
				}
				
			}
		}
	}
	
	int edge_size = edge.size();
	parent.resize(group_num+1);
	sort(edge.begin(), edge.end());
	for (int i = 0; i < group_num+1; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < edge_size; i++) {
		if (get_parent(edge[i].second.first) != get_parent(edge[i].second.second)) {
			union_parent(edge[i].second.first, edge[i].second.second);
			answer += edge[i].first;
		}
	}
	return answer;
}