가중치가 낮은 것(0) 은 앞에 unshift 시켜주고, 가중치가 높은 것(1) 은 push 시켜주어서 가중치가 낮은 것부터 bfs 탐색이 가능하게끔 한다.
bfs 와 다익스트라보다 시간 복잡도가 낮아 잘만 쓰면 유용하게 쓰일 것 같다.
bfs 할 때 가중치를 생각하면 빠르게 풀 수 있다.
관련 문제 풀이
BOJ- 벽 부수고 이동 2
난이도 : 골드 4
enqueue로만 구현해서 0-1 bfs 로 풀었다고 말할 수 있을지 모르겠다. JS는 덱이 구현되어있지 않기 때문에 처음에는 배열로 unshift, shift, push 를 이용하여 풀었는데 시간초과가 떴다. 그래서 Qeue 구현한 것을 가져와서 붙여넣으니 통과가 되었다.
👩💻 풀이 설명
✓ 부수고 이동하는 것은 가중치 1 로, 부수고 이동하지 않는 것은 0으로 둔다.
- 위에서도 언급했지만 enqueue로만으로도 풀리는 문제다. 그래서 0 이고 1이고 나눌 필요가 없다.
✓ visited[x][y][count] 는 x,y 만큼 이동하는데 count(벽을 부순 횟수) 만큼 걸렸다는 뜻이고, count 만큼 오는데 최소 경로다.
- 만약, visited[0][3][1]=3 이라면, graph[0][3] 까지 오는데 1번 벽을 부수고 3번 경로를 이동했다는 뜻이다.
✓ 따라서 답은 visited[n-1][m-1] 에서 최솟값이 정답이 된다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}
dequeue() {
if (!this.head) {
return null;
}
if (this.head === this.tail) {
this.tail = null;
}
const popped = this.head;
this.head = this.head.next;
this.length--;
return popped.value;
}
}
const inputs = require("fs")
.readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
.toString()
.split("\n");
const [n, m, k] = inputs.shift().split(" ").map(Number);
const graph = Array.from(Array(n), () => []);
const visited = Array.from(Array(n), () =>
Array.from(Array(m), () => Array(k + 1).fill(Infinity))
);
for (let i = 0; i < n; i++) {
graph[i] = inputs[i].split("").map(Number);
}
const solution = () => {
let answer = Infinity;
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const q = new Queue();
q.enqueue([0, 0, 0]);
visited[0][0][0] = 1;
while (q.length) {
const [x, y, count] = q.dequeue();
for (let i = 0; i < 4; i++) {
const [nx, ny] = [x + dx[i], y + dy[i]];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// 1. 벽을 깨는 경우 (가중치 +1)
if (graph[nx][ny]) {
const nCount = count + 1;
if (nCount > k) continue;
if (visited[nx][ny][nCount] > visited[x][y][count] + 1) {
// console.log(nx, ny);
visited[nx][ny][nCount] = visited[x][y][count] + 1;
q.enqueue([nx, ny, nCount]);
}
continue;
}
if (visited[nx][ny][count] > visited[x][y][count] + 1) {
visited[nx][ny][count] = visited[x][y][count] + 1;
q.enqueue([nx, ny, count]);
}
}
}
}
answer = Math.min(...visited[n - 1][m - 1], answer);
if (answer !== Infinity) return answer;
return -1;
};
console.log(solution());
BOJ-알고스팟
난이도 : 골드 4
위의 문제에서 최대 K만큼의 벽을 부술 수 있는 것과 달리
최소의 벽을 부숴서 도착할 수 있는 경우의 수를 고르는 문제다.
0-1 bfs 문제는 이럴 때 유용하게 쓰이는 것 같다.
👩💻 풀이 설명
✓ 1 인 경우는 벽이다.
- 가중치 1로 설정해준다.
✓ 0 인 경우는 이동할 수 있다.
- 가중치 0으로 설정해준다.
가중치 0인 것은 unshift 연산을 통해, 1인 것은 push 연산을 통해 가중치가 0인 것을 먼저 bfs 에서 우선적으로 탐색할 수 있도록 해준다.
visited[x][y] = x와 y 에 오는데 몇 개의 벽을 부수었는지 확인한다. x,y를 방문했을 때 최솟값이 들어오게 된다.
const inputs = require("fs")
.readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
.toString()
.split("\n");
const [m, n] = inputs.shift().split(" ").map(Number);
const board = Array.from(Array(n), () => []);
const visited = Array.from(Array(n), () => Array(m).fill(Infinity));
for (let i = 0; i < n; i++) {
board[i] = inputs[i].split("").map(Number);
}
const solution = () => {
const q = [[0, 0]];
visited[0][0] = 0;
let answer = Infinity;
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
while (q.length) {
const [x, y] = q.shift();
for (let i = 0; i < 4; i++) {
const [nx, ny] = [x + dx[i], y + dy[i]];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// 1. 벽이 존재하지 않을 때
if (!board[nx][ny] && visited[nx][ny] > visited[x][y]) {
q.unshift([nx, ny]);
visited[nx][ny] = visited[x][y];
continue;
}
// 2. 벽이 존재할 때
if (visited[nx][ny] > visited[x][y] + 1) {
q.push([nx, ny]);
visited[nx][ny] = visited[x][y] + 1;
}
}
}
}
answer = visited[n - 1][m - 1];
return answer;
};
console.log(solution());