문제 URL : https://programmers.co.kr/learn/courses/30/lessons/62050
코딩테스트 연습 - 지형 이동
[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18
programmers.co.kr
문제 접근법: 그림에 나와있는것처럼 높이 차가 height 이하인것들은 사다리없이 이동이 가능하기때문에
사다리 없이 이동가능한 지점들을 색깔별로 영역 표시를 해줍니다. BFS 나 DFS로 영역표시해주고 난다음
여기서부터 생각을 잘하셔야하는데 영역별로 다른영역으로 이동할수있는 지점들을 구해서
Kruskal 알고리즘을 사용하면 풀리는 문제였습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
//By 콩순이냉장고
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int visit[300][300];
int parent[90001];
typedef pair<int, int> p;
bool isrange(int y, int x)
{
if (0 <= y&&y < n && 0 <= x&&x < n)
return true;
return false;
}
int gap(int a, int b)
{
return a>b ? a - b : b - a;
}
void bfs(vector<vector<int>> &land, int y, int x, int color, int h)//색칠
{
queue<pair<int, int>> q;
q.push({ y, x });
visit[y][x] = color;
while (!q.empty())
{
y = q.front().first;
x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && !visit[ny][nx] && gap(land[y][x], land[ny][nx]) <= h)
{
q.push({ ny, nx });
visit[ny][nx] = color;
}
}
}
}
int find(int idx)
{
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}
int kruskal(vector<vector<int>> &land)
{
vector<pair<int, p>> v;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < 4; k++)
{
int ny = i + dy[k];
int nx = j + dx[k];
if (isrange(ny, nx) && visit[i][j] != visit[ny][nx])//다른영역을 해당되는 사다리를 설치해야할곳을 정함
v.push_back({ gap(land[i][j], land[ny][nx]), { visit[i][j], visit[ny][nx] } });
}
}
}
sort(v.begin(), v.end());//정렬을해주고
int sum = 0;
for (int i = 0; i < v.size(); i++)
{
int left = find(v[i].second.first);
int right = find(v[i].second.second);
if (left != right){//색칠한 영역들이 이어지지 않았다면 가장 적은 순서대로이어줌
parent[right] = left;
sum += v[i].first;
}
}
return sum;
}
int solution(vector<vector<int>> land, int height) {
int answer = 0;
n = land.size();
int color = 1;
for (int i = 0; i < n; i++)//영역을 색칠
{
for (int j = 0; j < n; j++)
{
if (!visit[i][j])
bfs(land, i, j, color++, height);
}
}
for (int i = 1; i < color; i++)//색칠한영역까지 부모들을 나눔
parent[i] = i;
return kruskal(land);
}
|
cs |
궁금한점 혹은 모르는점 또는 잘못생각한 점이 있다면 언제든 댓글을 이용해주시길 바랍니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 섬 연결하기 (0) | 2020.09.09 |
|---|---|
| 프로그래머스 [3차] 자동완성(2018 KAKAO BLIND RECRUITMENT) (0) | 2020.09.09 |
| 프로그래머스 [1차] 뉴스클러스터링(2018 KAKAO BLINED RECRUITMENT) (0) | 2020.09.09 |
| 프로그래머스 순위 (0) | 2020.08.30 |
| 프로그래머스 기지국설치 (0) | 2020.08.28 |
