<프로그래머스> 지형 이동

<링크>

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

프로그래머스

 

<문제>

• N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.
• 이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 
• 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다.
•  높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다.
•  이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다.
•  따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다.
• 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.
• 각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

<제한사항>

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

<입력 및 출력>

<아이디어>

1. 어... 이거 BFS.... MST...

2. unionFind 친구네..!

3. unionFind 쓰려면 이제.. Edge 클래스도 만들어서 풀어야 겠네 ㅠ

<풀이 - Java >

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {

	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	// 간선 클래스
	static class Edge {
		int from, to, weight;

		Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
	}

	// 유니온 파인드
	static class Union {
		int[] parent;

		Union(int size) {
			parent = new int[size];
			for (int i = 0; i < size; i++) {
				parent[i] = i;
			}
		}

		int findSet(int x) {
			if (parent[x] != x) {
				parent[x] = findSet(parent[x]);
			}
			return parent[x];
		}

		boolean union(int x, int y) {
			int rootX = findSet(x);
			int rootY = findSet(y);
			if (rootX != rootY) {
				parent[rootY] = rootX;
				return true;
			}
			return false;
		}
	}

	public int solution(int[][] land, int height) {
		int answer = 0;
		// 난 땅 길이
		int n = land.length;
		// Edge 담을 어레이 리슽
		List<Edge> edges = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 지금 높이
				int currentH = land[i][j];
				// 뱅뱅뱅
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					// 혹시. 범위를 벗어나지는 않았니?
					if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
						// 옮긴 뒤의 높이
						int neightH = land[nx][ny];
						// 차이를 넣어보아요
						int cost = Math.abs(currentH - neightH);

						// 이동 비용 담자 담아. 근데, 주어진 height보다 cost가 크다면 말이지.
						if (cost > height) {
							edges.add(new Edge(i * n + j, nx * n + ny, cost));
						} else {
							edges.add(new Edge(i * n + j, nx * n + ny, 0));
						}
					}
				}
			}
		}
		// 이거때문에 정렬로 정리된건 좀 너무하지 않니??
		Collections.sort(edges, Comparator.comparingInt(e -> e.weight));

		// union 크기만들고
		Union union = new Union(n * n);
		// 돌아용
		for (Edge edge : edges) {
			if (union.union(edge.from, edge.to)) {
				answer += edge.weight;
			}
		}

		return answer;
	}
}