https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
📌 작성한 코드
// 1260
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m, root] = input.shift().split(" ").map(Number);
const arr = input.map((i) => i.split(" ").map(Number));
const makeGraph = (list) => {
let graph = {};
for (const item of list) {
const [first, second] = item;
graph[first] ? graph[first].push(second) : (graph[first] = [second]);
graph[second] ? graph[second].push(first) : (graph[second] = [first]);
}
for (const item in graph) {
graph[item].sort((a, b) => a - b);
}
for (let i = 1; i <= n; i++) {
if (!graph[i]) graph[i] = [];
}
return graph;
};
const iterativeDfs = (graph, start) => {
const visited = new Array(n).fill(false);
const stack = [];
const order = [];
stack.push(start);
while (stack.length) {
const v = stack.pop();
if (!visited[v]) {
visited[v] = true;
order.push(v);
for (const node of graph[v]) {
if (!visited[node]) {
stack.push(node);
}
}
}
}
return order;
};
const order = [];
const recursiveDfs = (graph, start, visited) => {
visited[start] = true;
order.push(start);
for (const node of graph[start]) {
if (!visited[node]) {
recursiveDfs(graph, node, visited);
}
}
};
const bfs = (graph, start) => {
const visited = new Array(n).fill(false);
const queue = [];
const order = [];
queue.push(start);
visited[start] = true;
while (queue.length) {
const v = queue.shift();
order.push(v);
for (const node of graph[v]) {
if (!visited[node]) {
visited[node] = true;
queue.push(node);
}
}
}
return order;
};
const solution = () => {
const graph = makeGraph(arr);
const visited = new Array(n).fill(false);
recursiveDfs(graph, root, visited);
const dfsAnswer = order;
const bfsAnswer = bfs(graph, root);
console.log(dfsAnswer.join(" "));
console.log(bfsAnswer.join(" "));
};
solution();
📌풀이
인접 리스트가 주어졌을때 dfs와 bfs로 모든 노드를 방문하고 방문 순서를 출력하는 문제
1. 인접 리스트를 그래프 객체로 만들기
- 양방향 간선이기 때문에 양쪽의 간선에 모두 추가해준다.
- 방문할 수 있는 정점이 여러개인 경우에 정점의 수가 작은 것부터 차례대로 방문해야 하기 때문에 오름차순 정렬해준다
(* iterative에서는 내림차순 해줘야함)
const makeGraph = (list) => {
let graph = {};
for (const item of list) {
const [first, second] = item;
graph[first] ? graph[first].push(second) : (graph[first] = [second]);
graph[second] ? graph[second].push(first) : (graph[second] = [first]);
}
for (const item in graph) {
graph[item].sort((a, b) => a - b);
}
for (let i = 1; i <= n; i++) {
if (!graph[i]) graph[i] = [];
}
return graph;
};
2. dfs(recursive)
- 방문 순서를 저장하기 위해서 order 배열 사용 (전역변수로 선언해서 좋지 않을듯. 수정 방법을 찾아봐야겠다)
- visited도 마찬가지로 재귀 하면서 하나의 배열이 계속 사용되기 때문에 따로 받아오게 하였다.
- 첫번째 노드부터 방문하고, 첫번째 노드에 연결된 인접 노드를 기준으로 다시 dfs() 수행하는 재귀 방식으로 구현
const order = [];
const recursiveDfs = (graph, start, visited) => {
visited[start] = true;
order.push(start);
for (const node of graph[start]) {
if (!visited[node]) {
recursiveDfs(graph, node, visited);
}
}
};
3. dfs(iterative)
- 재귀가 아니라 stack에 node를 삽입하고 빼면서 방문하는 dfs
- 인접 노드들을 방문하면서 stack에 넣고, stack에서 하나를 꺼내서 다시 그 노드를 기준으로 인접노드 추가
-> 이렇게 하면 1: [2,3] 2 : [4] 3: [5] ... 이런 그래프가 있다고 했을 때
-> stack = [2,3] -> stack: [2] -> 3 빠져나옴 -> 3번 기준으로 인접노드 확인 -> 5 넣기 -> stack : [2,5]
=> 이렇게 되어서 깊이를 우선적으로 살펴보는 방식이 적용됨
* 이렇게하면 위의 예시에 봤듯이 2,3이 있을때 3을 먼저 방문하게 됨
-> 그래서 작은 순서대로 방문하게 하고 싶으면 그래프를 정리하는 함수에서 오름차순이 아니라 내림차순으로 저장되게 해줘야함
-> 그래서 이번 문제에서는 iterative가 아니라 recursive로 풀었다(재귀dfs와 bfs는 모두 오름차순 사용하면 작은 순으로 방문함)
const iterativeDfs = (graph, start) => {
const visited = new Array(n).fill(false);
const stack = [];
const order = [];
stack.push(start);
while (stack.length) {
const v = stack.pop();
if (!visited[v]) {
visited[v] = true;
order.push(v);
for (const node of graph[v]) {
if (!visited[node]) {
stack.push(node);
}
}
}
}
return order;
};
4. bfs
- bfs는 dfs와 비슷하지만 너비를 먼저 확인한다는 것이 차이점
- 인접한 노드를 저장하고 꺼낼 때 stack이 아니라 queue에 저장해서 인접한 노드들을 먼저 다 살피고 나서 다음 레벨로 내려가서 탐색한다
- queue를 사용하고 shift(), push() 사용
const bfs = (graph, start) => {
const visited = new Array(n).fill(false);
const queue = [];
const order = [];
queue.push(start);
visited[start] = true;
while (queue.length) {
const v = queue.shift();
order.push(v);
for (const node of graph[v]) {
if (!visited[node]) {
visited[node] = true;
queue.push(node);
}
}
}
return order;
};

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS] 백준 실버 1 : 2667 - 단지번호붙이기 (0) | 2023.09.12 |
|---|---|
| [JavaScript/DFS] 백준 실버 3 : 10451 - 순열 사이클 (0) | 2023.09.08 |
| [JavaScript/DP] 백준 실버 3 : 14501 - 퇴사 (0) | 2023.08.31 |
| [JavaScript/DFS] 백준 실버 1 : 14888 - 연산자 끼워넣기 (1) | 2023.08.18 |
| [JavaScript/BFS] 백준 골드 5 : 18405 - 경쟁적 전염 (0) | 2023.08.12 |