✔ 아래의 캡쳐본은 문제의 일부입니다.
보다 자세한 제한 사항 및 입출력 예시는 위의 링크를 참고해주세요!
💬 사담
잘 버티다가 결국 코로롱에 걸렸다..
상태가 조금 호전됐다고 생각해서 문제를 풀었는데 아직 두통이 있어서일까
맞왜틀의 연속이었다 😂
생각해보니 쉬운 문제라고 생각하여 문제를 완전히 분석하지 않은 상태에서
코드를 짜내려가기 시작했던 것 같다
부끄럽지만 그 과정을 그대로 적어보려고 한다..
하지만 자바스크립트에서 큐나 우선순위큐를 직접 구현해서 써야 한다는 사실은
조금 눈물난다..
C++로 풀었으면 이렇게 오래 걸리진 않았을 것 같다는
구차한 변명을 하며.. 복기 시-작 🤧
⭐ 풀이의 핵심
- BFS(DFS를 사용해도 무관)를 활용해서 풀 수 있는 문제였다
- 방향이 영향을 주기 때문에 visited check을 할 때 방향 플래그를 함께 저장하기 위해 visited 배열을 2차원이 아닌 3차원 배열로 선언하는 게 중요했다
visited[i][j][k]: k 방향에서 (i, j)에 도달했을 때의 price
- JavaScript에는 큐나 우선순위큐가 없으며 배열의 push와 shift 메서드를 활용하여 배열을 큐처럼 사용하게 될 경우 shift 메서드의 복잡도가 O(n)이기 때문에 시간초과가 날 확률이 높다 따라서 이와 같은 문제를 JavaScript로 풀 때에는 큐나 우선순위 큐를 직접 구현해서 써야 한다
🚨 첫 번째 시도
const solution = (board) => {
let answer = 2147483647;
const len = board.length;
// 위쪽 오른쪽 아래쪽 왼쪽
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const isOutOfRange = (r, c) => {
if (r < 0 || r >= len || c < 0 || c >= len) return true;
return false;
}
const queue = [[0, 0, -1, 0]];
const visited = Array.from(new Array(len), () => new Array(len).fill(0));
while (queue.length) {
const [row, col, dir, price] = queue.shift();
if (row === len - 1 && col === len - 1) {
answer = Math.min(answer, price);
}
for (let k=0; k<4; k++) {
// cf. 경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있음
const nextRow = row + dr[k];
const nextCol = col + dc[k];
// cf. 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냄
// cf. 벽이 있는 칸에는 경주로를 건설할 수 없음
if (isOutOfRange(nextRow, nextCol) || board[nextRow][nextCol] === 1) continue;
// cf. 건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며 코너를 하나 만들 때는 500원이 추가로 듬
let nextPrice = price;
nextPrice += 100;
if (dir % 2 === 0 && k % 2 === 1 || dir % 2 === 1 && k % 2 === 0) nextPrice += 500;
if (!visited[nextRow][nextCol] || visited[nextRow][nextCol] >= nextPrice) {
visited[nextRow][nextCol] = nextPrice;
queue.push([nextRow, nextCol, k, nextPrice]);
}
}
}
// 경주로를 건설하는데 필요한 최소 비용을 return
return visited[len-1][len-1];
}
👉 테케 25번 실패
- 방향(dir)이 위치 별 비용에 영향을 미친다는 것을 간과하고 작성한 코드
visited[i][j]2차원 배열에는 그 위치(i, j)까지의 최소비용을 담게 되는데, 이를visited[i][j][k]와 같이 3차원 배열로 수정하여 k 방향으로 해당 위치 (i, j)에 도달했을 때 최소비용을 저장하는 방식으로 접근해야함
[참고] 질문하기 | c++ 케이스 25
[참고] 질문하기 | (BFS + DP) 테스트 25 통과 안되시는 분들 참고하세요 (정답 코드 있음)
🚨 두 번째 시도
const solution = (board) => {
let answer = 2147483647;
const len = board.length;
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const isOutOfRange = (r, c) => {
if (r < 0 || r >= len || c < 0 || c >= len) return true;
return false;
}
const queue = [[0, 0, -1, 0]];
// 📌 visited 배열을 2차원 -> 3차원 배열로 수정
const visited = new Array(len);
for (let i=0; i<len; i++) {
visited[i] = new Array(len);
for (let j=0; j<len; j++) {
visited[i][j] = new Array(len);
}
}
while (queue.length) {
const [row, col, dir, price] = queue.shift();
if (row === len - 1 && col === len - 1) {
answer = Math.min(answer, price);
}
for (let k=0; k<4; k++) {
const nextRow = row + dr[k];
const nextCol = col + dc[k];
if (isOutOfRange(nextRow, nextCol) || board[nextRow][nextCol] === 1) continue;
let nextPrice = price;
nextPrice += 100;
if (dir % 2 === 0 && k % 2 === 1 || dir % 2 === 1 && k % 2 === 0) nextPrice += 500;
// 📌 visited 3번째 인덱스로 방향 플래그 설정
if (!visited[nextRow][nextCol][k] || visited[nextRow][nextCol][k] >= nextPrice) {
visited[nextRow][nextCol][k] = nextPrice;
queue.push([nextRow, nextCol, k, nextPrice]);
}
}
}
return answer;
}
👉 첫 번째 시도에서 통과하지 못했던 테케 25번 통과하였으나, 테케 11번, 19번에서 시간 초과 발생
- 큐를 직접 구현하지 않고 배열(Array)를 큐처럼 활용한 부분에서
Array.shift()의 복잡도가 O(1)이 아닌 O(n)이기 때문에 발생한 문제라고 예상 - 큐를 직접 구현해서 사용하기로 함 (앞서 언급한 바와 같이 JavaScript에는 큐가 없음.. 😥)
🚨 세 번째 시도
const solution = (board) => {
// 📌 큐 구현하여 활용
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.len = 0;
}
push(data) {
const newNode = new Node(data);
if (this.empty()) this.head = newNode;
else this.tail.next = newNode;
this.tail = newNode;
this.len++;
}
pop() {
if (!this.empty()) {
this.head = this.head.next;
this.len--;
}
}
front() {
return this.head.data;
}
empty() {
return this.len === 0;
}
}
let answer = 2147483647;
const len = board.length;
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const isOutOfRange = (r, c) => {
if (r < 0 || r >= len || c < 0 || c >= len) return true;
return false;
}
const q = new Queue();
q.push([0, 0, -1, 0]);
const visited = new Array(len);
for (let i=0; i<len; i++) {
visited[i] = new Array(len);
for (let j=0; j<len; j++) {
visited[i][j] = new Array(len);
}
}
while (!q.empty()) {
const [row, col, dir, price] = q.front();
q.pop();
if (row === len - 1 && col === len - 1) {
answer = Math.min(answer, price);
}
for (let k=0; k<4; k++) {
const nextRow = row + dr[k];
const nextCol = col + dc[k];
if (isOutOfRange(nextRow, nextCol) || board[nextRow][nextCol] === 1) continue;
let nextPrice = price;
nextPrice += 100;
if (dir % 2 === 0 && k % 2 === 1 || dir % 2 === 1 && k % 2 === 0) nextPrice += 500;
if (!visited[nextRow][nextCol][k] || visited[nextRow][nextCol][k] >= nextPrice) {
visited[nextRow][nextCol][k] = nextPrice;
q.push([nextRow, nextCol, k, nextPrice]);
}
}
}
return answer;
}
👉 테케 19번 해결 + 여전히 테케 11번 시간초과
- 비용이 작은 순으로 정렬되는 우선순위 큐를 활용하면 시간 복잡도를 개선할 수 있다는 글을 봄
- 이번에는 우선순위 큐를 직접 구현해서 사용하기로 함 (앞서 언급한 바와 같이 JavaScript에는 우선순위 큐도 없음.. 😂)
✅ 최종 코드
const solution = (board) => {
// 📌 우선순위 큐 구현하여 활용
class PriorityQueue {
constructor() {
this.heap = [];
}
getLeftChild = (parent) => parent * 2 + 1;
getRightChild = (parent) => parent * 2 + 2;
getParent = (child) => Math.floor((child - 1) / 2);
enqueue = (key, value) => {
const node = { key, value };
this.heap.push(node);
this.heapifyUp();
}
dequeue = () => {
const len = this.heap.length;
const root = this.heap[0];
if (len <= 0) return undefined;
if (len === 1) this.heap = [];
else {
this.heap[0] = this.heap.pop();
this.heapifyDown();
}
return root;
}
heapifyUp = () => {
let idx = this.heap.length - 1;
const lastEnqueued = this.heap[idx];
while (idx > 0) {
const parent = this.getParent(idx);
if (this.heap[parent].key > lastEnqueued.key) {
this.heap[idx] = this.heap[parent];
idx = parent;
}
else break;
this.heap[idx] = lastEnqueued;
}
}
heapifyDown = () => {
let idx = 0;
const len = this.heap.length;
const root = this.heap[idx];
while (this.getLeftChild(idx) < len) {
const leftChild = this.getLeftChild(idx);
const rightChild = this.getRightChild(idx);
const smallerChild = rightChild < len && this.heap[rightChild].key < this.heap[leftChild].key
? rightChild : leftChild;
if (this.heap[smallerChild].key <= root.key) {
this.heap[idx] = this.heap[smallerChild];
idx = smallerChild;
}
else break;
}
this.heap[idx] = root;
}
empty = () => this.heap.length === 0;
front = () => this.heap[0].value;
}
let answer = 2147483647;
const len = board.length;
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const isOutOfRange = (r, c) => {
if (r < 0 || r >= len || c < 0 || c >= len) return true;
return false;
}
const pq = new PriorityQueue();
pq.enqueue(0, [0, 0, -1, 0]);
const visited = new Array(len);
for (let i=0; i<len; i++) {
visited[i] = new Array(len);
for (let j=0; j<len; j++) {
visited[i][j] = new Array(len);
}
}
while (!pq.empty()) {
const [row, col, dir, price] = pq.front();
pq.dequeue();
if (row === len - 1 && col === len - 1) {
answer = Math.min(answer, price);
}
for (let k=0; k<4; k++) {
const nextRow = row + dr[k];
const nextCol = col + dc[k];
if (isOutOfRange(nextRow, nextCol) || board[nextRow][nextCol] === 1) continue;
let nextPrice = price;
nextPrice += 100;
if (dir % 2 === 0 && k % 2 === 1 || dir % 2 === 1 && k % 2 === 0) nextPrice += 500;
if (!visited[nextRow][nextCol][k] || visited[nextRow][nextCol][k] >= nextPrice) {
visited[nextRow][nextCol][k] = nextPrice;
pq.enqueue(nextPrice, [nextRow, nextCol, k, nextPrice]);
}
}
}
return answer;
}
👉 성공
우선순위 큐를 구현하는 로직의 경우 너무 오랜만이라 + 여러 번의 시도에 지친 상태여서.. 아래 참고 링크에 나온 코드를 따라서 복습하며 만들었습니다 😭
벨로그에는 주로 알고리즘 문제를 풀고 기록합니다 ✍