DFS와 BFS의 정석같은 문제이다.
DFS랑 BFS 문제는 몇 번 풀어봤는데 풀 때마다 헷갈림..
익숙해질 만큼 풀자!
쉽게 얘기하면 DFS는 아래로 계속 내려가고 BFS는 옆으로 계속 옮겨간다고 생각하면 된다.
그래서 DFS는 재귀나 stack을 사용하고
BFS는 queue를 사용해서 푼다.
위 문제는 모든 노드에 방문하는 문제라서 인접리스트를 사용해서 풀었다.
인접행렬을 사용해서 풀 경우 노드에 연결되지 않은 부분도 확인하기 때문에 시간복잡도가 더 증가한다.
예제가 아래와 같은 경우,
5 5 3
5 4
5 2
1 2
3 4
3 1
인접리스트를
1 [2, 3]
2 [1, 5]
3 [1, 4]
4 [3, 5]
5 [2, 4]
이렇게 만들 수 있다. (오름차순으로 정렬함)
DFS
로 탐색하는 경우
1. 시작점 3
에서 연결된 정점 중 가장 작은 정점 번호인 1
을 방문하고
2. 1
에서 연결된 가장 작은 정점 번호인 2
를 방문,
3. 2
에서 연결된 가장 작은 정점 번호가 1
이지만 1
은 이미 방문했기 때문에 통과하고 5
를 방문,
4. 5
에서 연결된 가장 작은 정점번호인 2
가 이미 방문했기 때문에 4
를 방문하고 끝난다.(모든 정점 순회)
따라서 3 -> 1 -> 2 -> 5 -> 4
가 나온다.
BFS
로 탐색하는 경우
1. 시작점 3
에서 연결된 정점중 가장 작은 정점 번호인 1
을 방문하고, 그 다음 정점 번호인 4
를 방문, 그리고 3
에서 연결된 정점이 더이상 없으므로 다음으로 넘어간다.
2. 시작점과 첫번째로 연결된 정점 1
과 연결된 2
와 3
을 방문하는데 3
은 이미 방문했으므로 넘어간다. 그리고 1
에서 연결된 정점이 없으므로 다음으로 넘어간다.
3. 시작점과 두번째로 연결된 정점 4
와 연결된 3
과 5
를 방문하는데 3
은 이미 방문했으므로 넘어간다. 그리고 모든 정점을 방문했으므로 종료한다.
따라서 3 -> 1 -> 4 -> 2 -> 5
가 된다.
// 인풋값 입력받기
let fs = require("fs");
let input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split("\n");
const [N, M, V] = input.shift().split(" ").map(Number);
const line = input.map((v) => v.split(" ").map(Number));
const ansDfs = [];
const ansBfs = [];
const graph = Array.from({ length: N + 1 }, () => []);
let visited = Array.from({ length: N + 1 }, () => 0);
const queue = [];
// 인접리스트 만들기
for (let [from, to] of line) {
graph[from].push(to);
graph[to].push(from);
// [1,2] 일 경우 1[2] 2[1] 두 가지 경우가 나온다.
}
for (let i = 1; i < graph.length; i++) {
graph[i].sort((a, b) => a - b);
// 정점 번호가 작은 것을 먼저 방문하기 때문에 오름차순으로 정렬한다.
}
function dfs(cnt) {
if (ansDfs.length === N) return;
// 최대 방문 정점 수는 최대 정점 번호보다 같거나 적어야 한다.
ansDfs.push(cnt);
visited[cnt] = 1;
for (let next of graph[cnt]) {
if (!visited[next]) {
visited[next] = 1;
dfs(next);
}
}
}
dfs(V);
visited = visited.map(() => 0);
// 방문한 정점 배열 초기화
function bfs() {
queue.push(V);
visited[V] = 1;
while (queue.length !== 0) {
const now = queue.shift();
ansBfs.push(now);
for (let next of graph[now]) {
if (!visited[next]) {
queue.push(next);
visited[next] = 1;
}
}
}
}
bfs();
console.log(ansDfs.join(" "));
console.log(ansBfs.join(" "));