옥수수밭
📚 문제 설명
N * M 크기의 옥수수밭이 있고 각각의 옥수수에는 숫자가 있다.
이 옥수수밭에서 농부가 K 그루의 옥수수만 수확하려고 한다. 옥수수는 바깥쪽과 인접한 경우에만 수확할 수 있다고 할 때, 농부가 수확한 옥수수의 숫자의 합이 최대가 되도록 하는 수확 순서를 구하여라.
👨🏻💻 풀이 과정
문제를 설명하기 앞서 미리 말하자면, 나는 첫 번째 풀이에서 실패했다.
순수하게 BFS만을 이용한 첫 번째 풀이에서 실패한 후에 우선순위 큐를 이용해야 한다는 사실을 알고 난 후에 통과를 받게 되었다.
그럼 첫 번째 풀이와 해당 풀이를 생각하게 된 사고 과정에 대해 설명하겠다.
💡 첫번쨰 풀이 (Fail)
첫번쨰 풀이는 BFS를 이용한 풀이이다.
- 옥수수밭 바깥으로 숫자 0인 부분을 만든다.
BFS()함수를 이용해 0, 0과 인접한 옥수수를 찾는다.- 0과 인접한 옥수수 중 가장 큰 값을 제거.
- 위의 과정
K번 반복.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [X, Y] = input.shift().split(' ').map(Number);
let MAP = input.splice(0, X).map(v => v.split(' ').map(Number));
// 옥수수밭 바깥쪽을 추가한 배열.
let newMAP = Array.from({length: X + 2}, _ => Array.from({length: Y + 2}, _ => 0));
let K = parseInt(input[0]);
// newMAP에 옥수수밭 값 추가.
MAP.forEach((Row, X) => {
Row.forEach((Corn, Y) => {
newMAP[X + 1][Y + 1] = Corn;
});
});
// BFS함수
const BFS = (start) => {
let Queue = [start];
let visited = Array.from({length: X + 2}, _ => Array.from({length: Y + 2}, _ => false));
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
// 최댓값 위치.
let max = [1, 1];
while (Queue.length) {
const [nowX, nowY] = Queue.shift();
visited[nowX][nowY] = true;
if (nowX < 0 || nowX >= X + 2 || nowY < 0 || nowY >= Y+ 2) continue;
for (let i = 0; i < dx.length; i++) {
const NextX = nowX + dx[i];
const NextY = nowY + dy[i];
// 범위 밖으로 나갈 경우 종료.
if (NextX < 0 || NextX >= X + 2 || NextY < 0 || NextY >= Y+ 2) continue;
if (!visited[NextX][NextY]) {
// 바깥과 인접한 옥수수인 경우.
if (newMAP[NextX][NextY] !== 0) {
visited[NextX][NextY] = true;
max = newMAP[NextX][NextY] > newMAP[max[0]][max[1]] ? [NextX, NextY] : max;
// 바깥쪽인 경우.
} else {
Queue.push([NextX, NextY]);
}
}
}
}
// 최댓값 위치 출력.
return max;
};
let answer = [];
// K번 반복.
while (K > 0) {
let [maxX, maxY] = BFS([0, 0]);
answer.push(`${maxX} ${maxY}`);
newMAP[maxX][maxY] = 0;
K--;
}
console.log(answer.join('\n'));
이 풀이에서의 최악의 경우를 살펴보자.
N과 M 이 1,000 이고, K는 100,000 이다.
그럼 최악의 경우 O( N X M X K ) 이 되고 100,000 * 100,000 이 된다.
따라서 문제 조건에 의해 시간 초과는 당연한 결과라고 볼 수 있다.
💡 두번쨰 풀이 (Success)
첫 번째 풀이가 실패한 이후, 도저히 BFS 방식만으로는 생각이 어려워서 문제 하단에 있는 알고리즘 분류를 확인했다.
그런데 거기서 우선순위 큐가 있는 것을 확인했고, 로직 전체를 다시 새로 작성했다.
[옥수수 값, 위치]를PQ에 넣어서 저장.PQ는 옥수수 값을 기준으로 내림차순 정렬.visited배열을 이용해 PQ에 넣은 옥수수 체크.- 테두리에 인접한 옥수수 모두 PQ에 삽입.
PQ에서 1개 제거, 제거한 옥수수와 인접한 옥수수를 다시PQ에 삽입. (K번 반복)
우선순위 큐 구현에 대한 설명은 생략하겠다.
만약 우선순위 큐 구현에 대한 설명이 필요하면 이전에 작성한 포스트 참고.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [X, Y] = input.shift().split(' ').map(Number);
let MAP = input.splice(0, X).map(v => v.split(' ').map(Number));
let K = parseInt(input[0]);
let visited = Array.from({length: X}, _ => Array.from({length: Y}, _ => false));
// 우선순위 큐.
// 우선순위 큐에 대한 주석은 생략.
class MaxHeap {
constructor() {
this.heap = [null];
}
Push(item) {
let current = this.heap.length;
while (current > 1) {
const Parent = Math.floor(current / 2);
if (this.heap[Parent][0] < item[0]) {
this.heap[current] = this.heap[Parent];
current = Parent;
}else break;
}
this.heap[current] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let Cur = 1;
let LeftChild = Cur * 2;
let RightChild = Cur * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild] && this.heap[LeftChild][0] < this.heap[RightChild][0]) {
Compare = RightChild;
}
if (this.heap[Compare][0] > this.heap[Cur][0]) {
[this.heap[Cur], this.heap[Compare]] = [this.heap[Compare], this.heap[Cur]];
Cur = Compare;
LeftChild = Cur * 2;
RightChild = Cur * 2 + 1;
}else break;
}
return PopItem;
}else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
Test() {
console.log(this.heap);
}
}
// 정답 배열.
let answer = [];
// 우선순위 큐 선언.
const PQ = new MaxHeap();
// 테두리에 위치한 옥수수 삽입.
for (let i = 0; i < X; i++) {
for (let j = 0; j < Y; j++) {
if (i === 0 || j === 0 || i === X - 1 || j === Y - 1) {
PQ.Push([MAP[i][j], i, j]);
visited[i][j] = true;
}
}
}
// K번 반복.
while (K > 0) {
let [num, nowX, nowY] = PQ.Pop();
let dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
// 제거한 옥수수 기준 인접한 옥수수 확인, 우선순위 큐에 삽입.
for (const dirElement of dir) {
const NextX = nowX + dirElement[0];
const NextY = nowY + dirElement[1];
// 범위 밖이라면 생략.
if (NextX < 0 || NextX >= X || NextY < 0 || NextY >= Y) continue;
// 큐에 옥수수 삽입.
if (!visited[NextX][NextY]) {
visited[NextX][NextY] = true;
PQ.Push([MAP[NextX][NextY], NextX, NextY]);
}
}
// 정답 추가.
answer.push(`${nowX + 1} ${nowY + 1}`);
K--;
}
console.log(answer.join('\n'));
중간의 런타임 에러의 경우 변수명을 너무 일관성 없이 써서 발생한 문제였다.
따라서 지역 변수명을 수정하니 해결되었다.
🧐 후기
오랜만에 우선순위 큐 문제였는데 전혀 우선순위 큐 문제라고 생각할 수가 없었다.
막상 우선순위 큐를 사용해야 한다는 사실을 알고 난 후에는 생각보다 쉽게 접근이 가능했다.
JavaScript를 사용하는 모두를 위해