(BFS에 대한 기본적인 지식이 있다고 가정하고 작성하였습니다. BFS에 대한 학습이 필요하면 여기를 참고해주세요)
BFS는 그래프 자료구조에서 유용하게 쓰이는 알고리즘이다.
백준 2178번에서 Time Out Error가 발생하여 이를 최적화한 과정을 기록하여 공유하고자 한다.
문제
전형적인 BFS 문제이며 로직은 다음과 같다.
- 시작점을 `queue`에 넣는다. ([row, col, 지금까지 거리] 형태로 넣어, 최소거리를 추적)
- `queue`의 길이가 0이 될때까지 다음 행동을 반복한다.
- 해당 지점으로부터 4방향중 이동가능한 방향을 찾는다.
- 이동가능한 방향을 큐에 넣는다.
- 이때, `queue`에서 꺼낸 위치가 최종 위치이면 최소값인지 판단하여 결과를 최신화한다.
// 최초 코드 (Time out Error)
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "../input.txt")
.toString()
.trim()
.split("\\n");
const [N, M] = input.shift().split(" ").map(Number);
const arr = input.map((subarr) => subarr.trim().split(""));
// # 방향 변수
const dr = [0, 1, 0, -1];
const dc = [1, 0, -1, 0];
const queue = [[0, 0, 1]];
let visited = Array.from(new Array(N), () => new Array(M).fill(false));
visited[0][0] = true;
let min = -1;
while (queue.length) {
const [row, col, cnt] = queue.shift();
visited[nrow][ncol] = true;
// # 도착 지점 도달
if (row === N - 1 && col === M - 1) {
min = min === -1 ? cnt : Math.min(min, cnt);
}
// # 도착 지점 이동중
else {
let i = 0;
for (i; i < 4; i++) {
const [nrow, ncol] = [row + dr[i], col + dc[i]];
if (
nrow >= 0 &&
nrow < N &&
ncol >= 0 &&
ncol < M &&
arr[nrow][ncol] === "1"
) {
queue.push([nrow, ncol, cnt + 1]);
}
}
}
}
console.log(min); // 결과 출력Time out Error가 발생하였다.
로직에는 전혀 문제가 없어 보였고, 최적화가 필요한 것 같았다.
시스템적 최적화 외 실행 횟수를 줄이기 위한 최적화를 하기 위해서는 `queue`에 들어가는 좌표의 개수를 줄이는 방법 밖에 없다.
그래서, `visited`에 집중하기 시작했다.
`visited`는 지금까지 방문한 노드와 방문하지 않은 노드를 구분하기 위해 사용하였다.
실제, BFS에서는 방문한 노드를 다시 방문하지 않기 때문이다. (그림 참고)
해당 문제는 모든 경로를 고려해야 한다고 판단하여, `visited[row][col] = true` 를 실제 방문했을 때 넣어주었던 것이다. 하지만, BFS의 개념에 대한 이해가 있었다면 이렇게 설정할 이유는 없다.
BFS는 DFS와 달리 같은 LEVEL의 노드들을 먼저 탐색한다.
즉, BFS를 진행하다가 어떤 좌표에 도달했다면, 해당 경로는 최소 경로가 된다.
따라서, 처음 최종 경로에 도달하는 경우가 최소 경로이다.
예를 들어,
| 출발 | 2 | 2 | 2 |
| 3 | 0 | 0 | 2 |
| 3 | 0 | 0 | 2 |
| 3 | 0 | 3 | 도착 |
| 3 | 3 | 3 | 0 |
이렇게 구성되어 있는 지도가 있다고 가정하자. (전체 좌표의 부분만을 예시로 설명합니다)
- 도착 위치까지 2로 이루어진 경로와 3로 이루어진 경로 2가지 경로가 존재한다.
- 2경로의 거리가 3경로의 거리보다 짧으며, BFS 로직 상 먼저 실행된다.
참고로, BFS의 Queue에 좌표를 추가하는 행위는 "해당 좌표로부터 최소 거리를 찾겠습니다.” 를 의미한다. - 결국, 나중에 도달한 방향(3경로)은 이미 최소 경로가 아니므로 고려할 필요가 없다.
설명이 길었습니다.
요약하자면
- `visited[row][col] = true`는 해당 위치가 valid한 위치라고 판단되었을때 바꿔주면 최적화가 가능합니다.
- 최종 위치에 도달하면 `break` 합니다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "../input.txt")
.toString()
.trim()
.split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const arr = input.map((subarr) => subarr.trim().split(""));
// # 방향 변수
const dr = [0, 1, 0, -1];
const dc = [1, 0, -1, 0];
const queue = [[0, 0, 1]];
let visited = Array.from(new Array(N), () => new Array(M).fill(false));
visited[0][0] = true;
let min = -1;
while (queue.length) {
const [row, col, cnt] = queue.shift();
// # 도착 지점 도달
if (row === N - 1 && col === M - 1) {
min = cnt;
break; // 한가지 밖에 없습니다.
}
// # 도착 지점 이동중
else {
let i = 0;
for (i; i < 4; i++) {
const [nrow, ncol] = [row + dr[i], col + dc[i]];
if (
nrow >= 0 &&
nrow < N &&
ncol >= 0 &&
ncol < M &&
arr[nrow][ncol] === "1" &&
!visited[nrow][ncol]
) {
queue.push([nrow, ncol, cnt + 1]);
visited[nrow][ncol] = true;
}
}
}
}
console.log(min);추가
만약에, 모든 경로를 구해야 하는 경우라면 처음에 했던 코드대로 진행해야 합니다.
참고 문헌
https://cdragon.tistory.com/entry/Algorithm-너비-우선-탐색BFS그래프-탐색
'PS > BFS+DFS' 카테고리의 다른 글
| [PS] 파이썬 BFS / DFS 구현방법 (2) | 2024.04.12 |
|---|