반응형
12-23 19:41
- Today
- Total
Link
개발하는 고라니
[Programmers] 지형 이동 본문
반응형
[Kruskal 알고리즘]
입력으로 들어오는 land[ ][ ]의 각 원소에 인덱스를 부여했다. 이차원 배열에서 인덱스를 부여하는 방법은 (i * N) + j 이다. 이렇게 하면 0부터 N-1 * N-1까지 원소에 대해 인덱스를 부여할 수 있다. 이는 곧 정점을 정의할 수 있다는 것이므로 크루스칼 알고리즘을 수행하기에 더욱 수월해진다.
우선 이중 for문을 돌며 land의 각 원소에 대해 상하좌우 정점 사이 간선의 정보를 만들어 List에 담는다.
for(int i=0; i<size; i++)
for(int j=0; j<size; j++) {
visit[i][j] = true;
int curH = land[i][j];
int home = (i * size) + j;
for (int a = 0; a < 4; a++) {
int ny = i + Y[a];
int nx = j + X[a];
if (ny < 0 || nx < 0 || ny > size - 1 || nx > size - 1 || visit[ny][nx]) continue;
int gap = Math.abs(curH - land[ny][nx]);
list.add(new Edge(home, (ny * size) + nx, (gap > height) ? gap : 0));
}
}
# Code </>
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
static class Edge implements Comparable<Edge>{
int h, tg, d;
public Edge(int home, int target, int dist){
h=home;
tg=target;
d=dist;
}
@Override
public int compareTo(Edge o) {
return d - o.d;
}
}
static List<Edge> list = new ArrayList<>();
static int[] parent = new int[90001], Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
static boolean[][] visit = new boolean[301][301];
static int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
static boolean findParent(int a, int b){
a = getParent(a);
b = getParent(b);
return a == b? true: false;
}
static void union(int a, int b){
a = getParent(a);
b = getParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
public int solution(int[][] land, int height) {
int size = land[0].length;
for(int i=0; i<size; i++)
for(int j=0; j<size; j++) {
visit[i][j] = true;
int curH = land[i][j];
int home = (i * size) + j;
for (int a = 0; a < 4; a++) {
int ny = i + Y[a];
int nx = j + X[a];
if (ny < 0 || nx < 0 || ny > size - 1 || nx > size - 1 || visit[ny][nx]) continue;
int gap = Math.abs(curH - land[ny][nx]);
list.add(new Edge(home, (ny * size) + nx, (gap > height) ? gap : 0));
}
}
for(int i=0; i<size*size; i++)
parent[i] = i;
Collections.sort(list);
int answer = 0;
for(Edge e : list)
if(!findParent(e.h, e.tg)){
answer += e.d;
union(e.h, e.tg);
}
return answer;
}
/*
public static void main(String[] args) {
int[][] land = {{10, 11, 10, 11}, {2, 21, 20, 10}, {1, 20, 21, 11}, {2, 1, 2, 1}};
//int[][] land = {{1, 4, 8, 10}, {5, 5, 5, 5}, {10, 10, 10, 10}, {10, 10, 10, 20}};
int height = 1;
System.out.println(solution(land, height));
}*/
}
반응형
'Programming > 프로그래머스' 카테고리의 다른 글
[Programmers] 순위 (0) | 2021.03.28 |
---|---|
[Programmers] 가장 먼 노드 (0) | 2021.03.28 |
[Programmers] 문자열 내 마음대로 정렬하기 (0) | 2021.03.17 |
[Programmers] 섬 연결하기 (0) | 2021.03.10 |
[Programmers] 크레인 인형 뽑기 게임 (0) | 2021.02.06 |
Comments