코딩테스트 연습 - 지형 이동
[[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
문제 설명
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 이하인 자연수입니다.
입출력 예
| land | height | result |
| [[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 |
입출력 예 #1
각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.
위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.
따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.
- 높이 5인 칸 → 높이 10인 칸 : 비용 5
- 높이 10인 칸 → 높이 20인 칸 : 비용 10
입출력 예 #2
각 칸의 높이는 다음과 같으며, 높이차가 1 이하인 경우 사다리 없이 이동이 가능합니다.
위 그림과 같이 (2행 1열) → (1행 1열), (1행 2열) → (2행 2열) 두 곳에 사다리를 설치하면 설치비용이 18로 최소가 됩니다.
풀이
두 가지 풀이 방법이 존재한다.
첫 번째 방법은 bfs와 우선순위큐를 응용하는 방법이다.
x값과 y값, 그리고 비용을 값으로 가지는 Point라는 객체를 만들고, 이를 담는 우선순위큐를 만든다.
우선순위큐는 비용을 기준으로 오름차순으로 저장되도록 한다.
이렇게 만들어진 큐를 이용해 bfs를 돌리게 되는데 다음 지형으로 이동할 때 사다리가 필요한 경우, 새로 큐에 들어갈 Point는 사다리 비용을 가지도록 하고, 사다리가 필요 없는 경우에는 비용을 0으로 가지도록 한다.
이렇게 구현하게되면 bfs는 자연스럽게 비용이 0인 사다리 없이 다닐 수 있는 칸을 우선적으로 순회하게 되고, 사다리가 필요한 경우도 최소의 비용이 드는 칸을 먼저 순회하게 된다.
즉, (사다리 없이 갈 수 있는 곳 우선 순회) -> (사다리가 필요한 곳 중 최소 비용이되는 곳으로 이동) -> (사다리를 탄 후 또 다른 사다리 없이 갈 수 있는 곳 우선 순회) -> ... 와 같은 순서로 탐색이 이뤄진다. 최소 비용이 아닌 사다리 필요한 칸은 자연스럽게 이미 방문한 곳이 되므로 없는 셈 치게 된다.
두 번째 방법은 크루스칼 알고리즘을 이용하는 방법이다.
크루스칼 알고리즘은 최소신장트리(MST)를 구할 때 이용하는 알고리즘으로 모든 노드를 탐색하기 위한 최소 비용을 구해야 하는 경우 이용된다.
이 문제에서는 사다리 없이 이동할 수 있는 칸들을 하나의 그룹으로 묶고 이 그룹이 크루스칼 알고리즘을 적용할 하나의 노드로 본다. 그리고 사다리 비용은 노드와 노드 사이를 이동할 때 필요한 가중치로 볼 수 있다.
큰 흐름은 다음과 같다.
1. bfs를 이용하여 사다리 없이 이동할 수 있는 지형을 그룹화한다.
2. 그룹들의 경계를 찾아 최소 사다리 비용을 찾는다.
3. 크루스칼 알고리즘을 적용하여 최소신장트리 비용을 찾아 값을 도출한다.
크루스칼 알고리즘을 적용할 때는 가중치가 가장 작은 부분부터 경로를 차례대로 추가한다. 이 작업을 위해서 2번에서 그룹들 간 최소 사다리 비용을 찾아논 것을 오름차순으로 정렬할 필요가 있는데, 정렬 효율을 위해서 우선순위큐를 활용해봤다.
이 우선순위큐에는 사실 최소 사다리 비용만이 아니라 모든 경계면의 값들이 담긴다. 오름차순이기 때문에 그렇기 때문에 큐에서 값을 꺼내 사용할 때 큐가 비게 될 때까지가 아니라 그룹 갯수 만큼만 수행하도록 한다.
크루스칼 알고리즘에서 최소신장트리를 만족하는 조건에는 사이클이 없어야한다는 조건이 있다. 사이클의 여부를 판별하기 위해서 유니온-파인드 알고리즘을 사용할 필요가 있었다. 크루스칼 알고리즘의 자세한 내용은 아래 링크를 참고하였다.
[알고리즘] Kruskal 알고리즘 이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
효율이나 코드 작성하는 시간을 생각해보면 사실 첫번째 방식이 더 좋았다고 생각했지만, 크루스칼 알고리즘과 유니온-파인드 알고리즘을 이용하는 것을 연습하기 위해서 두 번째 방법에 대해 조금 더 많이 고민하고 숙지하려고 노력했던 문제였다.
시간이 지나 망각의 곡선 쿨타임이 차게된다면 다시 풀어볼만한 문제라고 생각한다.
코드1 - 우선순위큐를 응용
import java.util.PriorityQueue;
import java.util.Queue;
public class Solution {
private static int[] x_move = {1, 0, -1, 0};
private static int[] y_move = {0, 1, 0, -1};
private int n;
public int solution(int[][] land, int height) {
int answer = 0;
n = land.length;
boolean[][] visited = new boolean[n][n];
Queue<Point> queue = new PriorityQueue<>();
queue.add(new Point(0, 0, 0));
while (!queue.isEmpty()) {
Point current = queue.poll();
if (visited[current.x][current.y]) {
continue;
}
visited[current.x][current.y] = true;
answer += current.value;
for (int i = 0; i < 4; i++) {
int nextX = current.x + x_move[i];
int nextY = current.y + y_move[i];
if (!isInArea(nextX, nextY)) {
continue;
}
int cost = Math.abs(land[current.x][current.y] - land[nextX][nextY]);
if (cost > height) {
queue.add(new Point(nextX, nextY, cost));
continue;
}
queue.add(new Point(nextX, nextY, 0));
}
}
return answer;
}
private boolean isInArea(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n;
}
class Point implements Comparable<Point> {
int x;
int y;
int value;
public Point(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
@Override
public int compareTo(Point o) {
return this.value - o.value;
}
}
}
코드2 - 크루스칼 알고리즘 이용
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class T35 {
private static int[] x_move = {1, 0, -1, 0};
private static int[] y_move = {0, 1, 0, -1};
private int n;
private int[][] groups;
private int[] parents;
// 크루스칼 알고리즘 이용한 풀이
public int solution(int[][] land, int height) {
int answer = 0;
n = land.length;
// bfs로 그룹핑
groups = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(groups[i], -1);
}
int group = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (groups[i][j] != -1) {
continue;
}
makeGroup(i, j, group, height, land);
group++;
}
}
// 경계가 되는 지형 및 사다리 비용 찾기
Queue<Node> heap = new PriorityQueue<>(); // 비용 기준 오름차순을 위해 우선순위큐 이용
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 4; k++) {
int x = i + x_move[k];
int y = j + y_move[k];
if (!isInArea(x, y)) {
continue;
}
if (groups[i][j] == groups[x][y]) { // 그룹이 같은 경우는 고려하지 않음
continue;
}
// 경계가 되는 두 그룹의 번호와 사다리 비용을 저장하여 우선순위큐에 저장
heap.add(new Node(groups[i][j], groups[x][y], Math.abs(land[i][j] - land[x][y])));
}
}
}
// 크루스칼 알고리즘 적용하여 최소 비용을 구함
// 유니온-파인드 알고리즘을 사용하여 사이클 여부를 파악
parents = new int[group];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
int count = 0;
while (!heap.isEmpty()) {
if (count == group) { // count가 그룹의 갯수와 동일해질 때까지만 수행
break;
}
Node node = heap.poll();
int prev = node.prev;
int next = node.next;
int weight = node.weight;
if (find(prev) == find(next)) {
continue;
}
union(prev, next);
answer += weight;
count++;
}
return answer;
}
private int find(int group) {
if (parents[group] == group) {
return group;
}
return find(parents[group]);
}
private void union(int prev, int next) {
int prevParent = find(prev);
int nextParent = find(next);
// 일관성을 위해 그룹 번호가 작은 쪽이 부모가 되도록 함
parents[Math.max(prevParent, nextParent)] = Math.min(prevParent, nextParent);
}
private void makeGroup(int x, int y, int group, int height, int[][] land) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
while (!queue.isEmpty()) {
Point current = queue.poll();
if (groups[current.x][current.y] != -1) {
continue;
}
groups[current.x][current.y] = group;
for (int i = 0; i < 4; i++) {
int nextX = current.x + x_move[i];
int nextY = current.y + y_move[i];
if (!isInArea(nextX, nextY)) {
continue;
}
if (Math.abs(land[current.x][current.y] - land[nextX][nextY]) > height) {
continue;
}
queue.add(new Point(nextX, nextY));
}
}
}
class Node implements Comparable<Node> {
private int prev;
private int next;
private int weight;
public Node(int prev, int next, int weight) {
this.prev = prev;
this.next = next;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private boolean isInArea(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n;
}
}'Tech > Problem Solving' 카테고리의 다른 글
| [프로그래머스] 2021 카카오 채용연계형 인턴십 - 미로 탈출 (Java) (0) | 2022.02.11 |
|---|---|
| [프로그래머스] 스택/큐 - 다리를 지나는 트럭 (Java) (0) | 2022.02.08 |
| [프로그래머스] 2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금 (Java) (0) | 2022.02.05 |
| [프로그래머스] Summer/Winter Coding(~2018) - 배달 (Java) (0) | 2022.02.04 |
| [프로그래머스] 월간 코드 챌린지 시즌2 - 괄호 회전하기 (Java) (0) | 2022.02.03 |
