해당 포스팅은 백준 1260번 DFS와 BFS 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성하였다.
정점 번호가 작은 것을 먼저 방문
하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 1번부터 N번
까지이다.정점의 개수 N(1 ≤ N ≤ 1,000)
, 간선의 개수 M(1 ≤ M ≤ 10,000)
, 탐색을 시작할 정점의 번호 V
가 주어진다. 간선이 연결하는 두 정점의 번호
가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이
다.첫째 줄에 DFS를 수행한 결과
를, 그 다음 줄에는 BFS를 수행한 결과
를 출력한다.
V부터 방문된 점을 순서대로 출력하면 된다.
예제의 인풋으로 인접 리스트
의 연결된 간선들이 주어진다. 시작점이 주어질 때 DFS와 BFS 수행 결과를 출력하라고 명시되어 있다.
따라서 인풋으로 주어지는 간선들을 연결해 그래프(인접 리스트)
를 구현한 다음, DFS와 BFS 함수를 구현해 각 수행결과를 출력하면 된다.
이 때 문제에서 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하라고 나와있으므로, 간선들을 연결한 다음 각 정점에 연결된 정점들을 오름차순 정렬
해야 한다.
예제를 통해 로직을 자세하게 설명하겠다.
문제의 예제2를 통해 자세한 로직을 설명하겠다.
위의 예제의 input을 파싱하면 다음과 같다.
먼저 인접 리스트를 만들기 위해 1) 정점들 생성, 2) 간선 연결을 한다.
그렇게 연결을 하면 그래프는 아래와 같이 만들어진다.
연결을 할 때 각 정점에 연결된 정점 list가 오름차순 정렬되어 있지 않음을 확인할 수 있다. 문제에서 뱡문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
하라고 나와있으므로 각 정점 list들을 오름차순 정렬하자.
오름차순 정렬을 하게되면 맨 오른쪽 그래프가 만들어지게 된다. 이제 해당 그래프를 DFS, BFS하면 된다.
위의 로직들을 코드로 옮기면 다음과 같다.
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);
let [N, M, V] = input[0].split(" ").map(Number);
let graph = [...Array(N+1)].map(()=>[]);
// 그래프 정점 생성
for (let i = 1; i <= M; i++) {
let [from, to] = input[i].split(" ").map(Number);
graph[from].push(to);
graph[to].push(from);
}
// 그래프 각 정점에 연결된 정점 LIST 오름차순 정렬
graph.forEach((element) => {
element.sort((a, b) => a - b);
});
// DFS
const visited_dfs = new Array(N + 1).fill(false);
const answer_dfs = [];
function dfs(V) {
if (visited_dfs[V]) return;
answer_dfs.push(V);
visited_dfs[V] = true;
graph[V].forEach((next) => {
if (visited_dfs[next] === false) {
dfs(next);
}
})
}
dfs(V);
console.log(answer_dfs.join(" "));
// BFS
const visited_bfs = new Array(N + 1).fill(false);
const answer_bfs = [];
function bfs(V) {
const queue = [V];
while (queue.length) {
const curr = queue.shift();
if (visited_bfs[curr] === true) continue;
visited_bfs[curr] = true;
answer_bfs.push(curr);
graph[curr].forEach((next) => {
if (visited_bfs[next] === false) {
queue.push(next);
}
})
}
}
bfs(V);
console.log(answer_bfs.join(" "));