문제
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 |
풀이
2019 Summer/Winter Coding 에서 출제된 문제이다. 꽤나 구현력도 요구하고 적절한 알고리즘을 적용할 사고력도 동시에 요구하는 문제인듯 하다. 하나씩 차근차근 살펴보며 문제를 풀어보자.
1) 사다리 없이 다닐 수 있는 영역 구분
land 배열은 2차원 배열로 각 칸의 높이를 갖고 있는 NxN 크기의 격자무늬로 볼 수 있다. 이때 각 칸은 height 보다 그 차가 같거나 작다면 사다리 없이 자유롭게 넘나들 수 있고, 반대로 칸의 격차가 이 보다 크다면 사다리를 설치해야 건너갈 수 있다. 이때 사다리 설치 비용은 두 칸의 격차만큼 소모된다.
이를 통해 우리가 알 수 있는 점은 사다리를 설치해야할 경계지점을 탐색해야 하는 것이다. 이는 각 칸을 하나의 노드로 본다면 그래프 탐색 알고리즘을 이용해서 사다리 없이 방문할 수 있는 영역을 구분지어 볼 수 있다. 방문 여부를 체크하는 것은 BFS 또는 DFS 중 어느 것을 선택하더라도 상관 없지만 개인적으로 자바스크립트에서 DFS를 꼭 필요한 경우가 아니라면 선호하지 않기 때문에 BFS 알고리즘을 통해 구현해보자.
먼저 주어진 격자에서 상하좌우 4가지 방향으로 진행할 수 있다. 일단 상하좌우를 결정할 방향 지시자와 방문여부를 저장할 배열, 그리고 실제 각 칸의 높이를 가지고 있는 배열을 하나씩 선언해주자.
// 상하좌우 4가지 이동방향을 설정하기 위한 x축 및 y축 좌표값
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];const len = land.length;
// 각 배열은 원래 배열 land보다 상하좌우 1만큼 큰 크기로 생성
// 이는 상하좌우 4가지 방향으로 움직이는 경우를 고려하기 위함
// board는 0으로, visited는 -1로 초기화
// 미방문 여부를 visited[i][j]가 0일때로 확인할 것이기 때문
const board = new Array(len+2).fill().map(_ => new Array(len+2).fill(0));
const visited = new Array(len+2).fill().map(_ => new Array(len+2).fill(-1));
// land 배열과 일치하는 영역은 동일하게 변경
// visited는 일치하는 영역을 모두 미방문 값인 0으로 변경
for(let i = 0; i < len; i++) {
for(let j = 0; j < len; j++) {
board[i+1][j+1] = land[i][j];
visited[i+1][j+1] = 0;
}
}그리고 이를 이용해 BFS 알고리즘을 구현해주자. 일반적인 BFS 알고리즘과 동일하게 구현해주면 된다. 다만 진행하려고 하는 곳의 높이와 현재 높이의 차가 height 보다 작거나 같을 때만 방문이 가능하다는 조건이 같이 고려되어야 하며, 제일 중요한 것은 사다리 없이 방문할 수 없는 영역을 동일 레벨로 그룹핑하는 것이다. 이를 위해 별도의 변수 groupNum을 넘겨주고, BFS의 deps가 깊어질 때마다 해당 값을 증가시켜주자. 그리고 이 값을 visited 배열의 방문여부 값으로 사용한다면, 동일한 값을 가진 모든 칸은 서로 사다리 없이 방문이 가능하다는 것을 나타낼 수 있다.
// 그루핑을 위한 넘버, 사실상 deps의 의미와 동일하다
let groupdNum = 1;
for(let i = 0; i < visited.length; i++) {
for(let j = 0; j < visited.length; i++) {
// 아직 방문하지 않은 경우 BFS 탐색 실시
if(!visited[i][j]) {
groupLandWithBFS(i, j, board, visited, height, groupNum++);
}
}
}// BFS 탐색 알고리즘을 이용해 사디리 없이 방문 가능한 영역 그룹핑 함수
const groupLandWithBFS = (y, x, board, visited, height, groupNum) => {
const queue = [ [y, x] ];
visited[y][x] = groupNum;
while(queue.length) {
const [y, x] = queue.shift();
const cur = board[y][x];
// 갈 수 있는 방향 탐색
for(let i = 0; i < 4; i++) {
const ny = dy[i] + y;
const nx = dx[i] + x;
const distance = Math.abs(cur - board[ny][nx]);
// 이동방향으로 진행된 좌표를 아직 방문하지 않고
if (!visited[ny][nx]) {
// 해당 좌표와 현재 좌표 높이차가 사다리가 필요없다면
if (distance <= height) {
// 방문처리
visited[ny][nx] = groupNum;
queue.push([ny, nx]);
}
}
}
}
}위 코드를 실행하고 나면 visited 배열에는 BFS 알고리즘이 돌며 기록한 각각의 deps가 기록되어 있을 것이다. 이때 같은 값을 공유하고 있는 칸은 모두 사다리 없이 방문할 수 있는 범위를 말한다. 우리는 이 값을 가지고 다음 작업을 진행할 것이다.
2) 사다리 설치 경계 지점 파악
visited 배열엔 방문여부가 서로 다른 그룹넘버로 마킹되어 있다. 서로 다른 넘버를 가지고 있다는 것은 두 영역 어딘가에서는 최소 하나 이상의 사다리가 설치되어야 한다는 것을 의미한다. 이때 우리는 최소 비용을 찾아야 하기 때문에, 두 영역을 이어주는 칸끼리의 높이차가 가장 낮은 두 지점을 찾아야 한다.
이를 위해 서로 다른 넘버를 가지고 있는 칸들을 비교하면서 이들의 높이차와 두 칸의 그룹넘버를 기록할 배열을 하나 만들도록 하자. 사다리는 접점이 있는 칸 사이에 설치되기 때문에, BFS 탐색 알고리즘때와 마찬가지로 4가지 방향으로 진행하면서 접점에서의 높이차와 넘버를 모두 저장하면 된다. 이때 그룹넘버를 따로 저장하는 이유는 밑에서 자세히 살펴보도록 하자.
// [ 높이차, [X의 그룹넘버, Y의 그룹넘버] ] 형태로 저장
const posInfoWithDistance = [];
for(let i = 0; i < visited.length; i++) {
for(let j = 0; j < visited.length; j++) {
for(let k = 0; k < 4; k++) {
const ny = i + dy[k];
const nx = j + dx[k];
// 서로 같은 그룹넘버가 아니면서
// 유효 범위 내에 위치한 칸에 대해서만 정보 취합
if ( visited[i][j] !== -1 &&
visited[ny][nx] !== -1 &&
visited[i][j] !== visited[ny][nx]) {
const distance = Math.abs(board[i][j] - board[ny][nx]);
posInfoWithDistance.push([ distance, [ visited[i][j], visited[ny][nx] ] ]);
}
}
}
}3) 모든 영역을 사다리 설치로 이어주기
posInfoWithDistance 배열에는 높이차와 함께 각각의 그룹넘버 정보가 저장되어 있다. 이때 높이차가 적을 수록 사다리 설치 비용이 최소가 되기 때문에 해당 배열을 높이차를 기준으로 오름차순 정렬 해주도록 하자. 이를 통해 가장 앞에 있는 원소가 제일 적은 높이차를 가지고 있게 될 것이다.
// 높이차는 첫 번째 원소에 들어있으므로
posInfoWithDistance.sort((a, b) => a[0] - b[0]);문제는 사다리 설치 비용을 최소로 하기 위해서는, 두 개의 영역에 단 하나의 사다리만 설치해야 한다는 점이다. 그리고 사다리가 설치된 영역은 다시 하나의 영역으로 탈바꿈된다. 왜냐하면 사다리를 통해 서로 건너갈 수 있는 범위가 되기 때문이다. 이를 확장하면 다음의 사실을 알 수 있다.
groupNum의 값 보다 1만큼 작은 사다리가 설치
groupNum은 현재 주어진 모든 범위에 존재하고 있는 독립된 영역의 개수와도 같다. 이 영역을 모두 이어주기 위해서는 두 영역에 단 한 개의 사다리만 필요하고, 사다리가 설치되면 이는 하나의 영역으로 간주되기 때문에 영역개수 - 1개의 사다리가 필요한 것이다.
따라서 우리는 두 영역 사이에서 가장 작은 높이차를 가진 두 칸의 접점에 사다리를 설치해야 한다. 그리고 두 그룹넘버는 이제 서로 통행이 가능하기 때문에 동일한 그룹넘버를 공유하도록 변경해야 할 것이다. 우리는 앞서 Lv.3 문제를 풀면서 위와 유사한 매커니즘을 볼 수 있었는데, 이는 대표적인 Union-Find 알고리즘이다. 해당 알고리즘은 Lv.3 섬 연결하기 문제 풀이에서도 설명한 바 있다.
두 개의 영역을 서로 합쳐 하나의 영역으로 만드는 과정은 결국 두 개 영역이 하나의 영역이 됨으로써 공통의 그룹넘버를 가지는 것과 같다. 즉 이 그룹넘버를 동일한 부모를 공유하고 있는지에 대한 체크섬으로 사용하고, 그룹넘버가 서로 다르다면 두 영역을 하나로 합쳐주도록 하자. 이를 위해 먼저 Union-Find 알고리즘을 적용하기 위한 함수를 구현해주자.
// 재귀 호출을 통해 부모를 찾는 함수
// 계속 부모로 올라가며 공동 부모를 가진 값을 반환
const findParent = (arr, n) => {
if (arr[n] === n) return n;
return findParent(arr, arr[n]);
}
// 두 노드의 부모를 찾아 공동 부모를 가지도록 단일화
// 보통 작은 값을 부모 값으로 지정
const unionParent = (arr, a, b) => {
a = findParent(arr, a);
b = findParent(arr, b);
if (a < b) arr[b] = a;
else arr[a] = b;
}
// 두 노드의 부모가 서로 같은지 판별
const isSameParent = (arr, a, b) => {
a = findParent(arr, a);
b = findParent(arr, b);
return a === b;
}이를 이용해서 서로 다른 그룹넘버에 가장 작은 높이차를 가진 접점에 사다리를 설치하고, 합쳐주도록 하자.
// 처음 부모 넘버는 자기 자신이 되도록 설정해주자
// 초기 그룹넘버는 1부터 시작하기 때문에 크기는 groupNum-1과 동일
const parents = new Array(groupNum-1).fill(0);
for(let i = 1; i < groupNum; i++) {
parents[i] = i;
}
// 사다리 설치 비용을 저장할 변수; 리턴값
let answer = 0;
// posInfoWithDistance는 높이차를 기준으로 오름차순 정렬된 상태
// 모든 노드에 대해 반복해도 상관없다
// 최대 크기가 90000이기 때문에 시간 초과가 발생할 염려가 적음
for (const node of posInfoWithDistance) {
const [ distance, [e1, e2] ] = node;
// 두 영역이 서로 같은 부모 넘버를 공유하고 있지 않다면
// 둘은 서로 다른 영역을 의미하기 때문에
if (!isSameParent(e1, e2)) {
// 사다리를 하나 설치하고
answer += distance;
// 동일한 부모 넘버를 공유하도록 단일화
unionParent(parents, e1, e2);
// 이후 시점에서 두 영역은 하나의 영역이 되었기 때문에
// 다시 두 영역이 등장해도 하나의 영역으로 간주하여
// 더 이상 사다리 설치를 하지 않음
}
}
return answer;4) 전체코드
코드가 좀 길어진 감이 있지만, 사실 대단히 복잡하고 어려운 내용은 없다고 생각한다. 적절한 그래프 탐색 알고리즘을 조건에 맞게 구현하는 것과 Union-Find 알고리즘을 사용하여 모든 영역을 하나로 합쳐주는 생각을 떠올릴 수 있었다면 큰 어려움 없이 풀 수 있었을 문제로 생각된다. 약간 무리하게 모든 유틸성 기능을 외부 함수로 만드려고 했기 때문에, BFS 탐색 함수의 경우 전달받는 매개변수가 너무 많아진 감이 있다. 이러한 컨벤션은 좋지 못한 코드에 속하기 때문에 solution 함수 내부에서 BFS 탐색을 직접 돌리거나 다른 방식을 고안하는 것도 추천한다. 주석을 제외한 전체코드는 다음과 같다.
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
function solution (land, height) {
const len = land.length;
const board = new Array(len+2).fill().map(_ => new Array(len+2).fill(0));
const visited = new Array(len+2).fill().map(_ => new Array(len+2).fill(-1));
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
board[i+1][j+1] = land[i][j];
visited[i+1][j+1] = 0;
}
}
let groupNum = 1;
for (let i = 0; i < len+2; i++) {
for (let j = 0; j < len+2; j++) {
if (!visited[i][j]) {
groupLandWithBFS(i, j, board, visited, height, groupNum++);
}
}
}
const posInfoWithDistance = [];
for (let i = 0; i < len+2; i++) {
for (let j = 0; j < len+2; j++) {
for (let k = 0; k < 4; k++) {
const ny = i + dy[k];
const nx = j + dx[k];
if (visited[i][j] !== -1 && visited[ny][nx] !== -1 &&
visited[i][j] !== visited[ny][nx]) {
const distance = Math.abs(board[ny][nx] - board[i][j]);
posInfoWithDistance.push([distance, [visited[i][j], visited[ny][nx]]]);
}
}
}
}
posInfoWithDistance.sort((a, b) => a[0] - b[0]);
const parents = new Array(groupNum-1).fill(0);
for (let i = 1; i < groupNum; i++) {
parents[i] = i;
}
let answer = 0;
for (const node of posInfoWithDistance) {
const [ distance, [ e1, e2 ] ] = node;
if (!isSameParent(parents, e1, e2)) {
answer += distance;
unionParent(parents, e1, e2);
}
}
return answer;
}
const groupLandWithBFS = (y, x, board, visited, height, groupNum) => {
const queue = [ [y, x] ];
visited[y][x] = groupNum;
while(queue.length) {
const [y, x] = queue.shift();
const cur = board[y][x];
for(let i = 0; i < 4; i++) {
const ny = y + dy[i];
const nx = x + dx[i];
const distance = Math.abs(board[ny][nx] - cur);
if (!visited[ny][nx]) {
if (distance <= height) {
visited[ny][nx] = groupNum;
queue.push([ny, nx]);
}
}
}
}
}
const findParent = (arr, n) => {
if (arr[n] === n) return n;
return findParent(arr, arr[n]);
}
const unionParent = (arr, a, b) => {
a = findParent(arr, a);
b = findParent(arr, b);
if (a < b) arr[b] = a;
else arr[a] = b;
}
const isSameParent = (arr, a, b) => {
a = findParent(arr, a);
b = findParent(arr, b);
return a === b;
}
출처
