[백준 DFS/BFS]문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4예제 출력 1
1 2 4 3
1 2 3 4예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1예제 출력 2
3 1 2 5 4
3 1 4 2 5예제 입력 3
1000 1 1000
999 1000예제 출력 3
1000 999
1000 999나의 코드
const inputFileName =
process.platform === "linux" ? "/dev/stdin" : "example.txt";
const input = require("fs")
.readFileSync(inputFileName)
.toString()
.trim()
.split("\n")
.map((r) => r.split(" ").map(Number));
const [[N, M, V], ...nodes] = input;
// DFS
function dfs() {
let graph = [...Array(N + 1)].map(() => []);
for (let [u, w] of nodes) {
graph[u].push(w);
if (!graph[w].includes(u)) {
graph[w].push(u);
}
}
graph.forEach((el) => el.sort((a, b) => b - a));
let visited = [];
let stack = [V];
while (stack.length) {
let currentNode = stack.pop();
if (!visited.includes(currentNode)) {
visited.push(currentNode);
}
for (let nextNode of graph[currentNode]) {
if (!visited.includes(nextNode)) {
stack.push(nextNode);
}
}
}
return visited;
}
console.log(dfs().join(" "));
// ------------------------------------
// BFS
function bfs() {
let graph = [...Array(N + 1)].map(() => []);
for (let [u, w] of nodes) {
graph[u].push(w);
if (!graph[w].includes(u)) {
graph[w].push(u);
}
}
graph.forEach((el) => el.sort((a, b) => a - b));
let visited = [];
let queue = [V];
while (queue.length) {
let currentNode = queue.shift();
if (!visited.includes(currentNode)) {
visited.push(currentNode);
}
for (let nextNode of graph[currentNode]) {
if (!visited.includes(nextNode)) {
queue.push(nextNode);
}
}
}
return visited;
}
console.log(bfs().join(" "));여태까지 DFS와 BFS 풀면서 그래프 문제는 나름 자신감이 붙었다고 생각했는데, 다익스트라 풀면서 생각보다 기초가 부실했다는 걸 많이 느꼈다. 그래서 DFS와 BFS의 가장 기본이 되는 문제를 풀어보았다. 마침 오늘 코플릿에서도 DFS 문제가 나왔는데 한 번 풀어보니 도움이 되었다. 우선 위의 코드 리뷰를 해보고 코플릿 문제도 마지막에 리뷰를 적어봐야겠다.
우선 이 문제는 간선이 양방향이므로, graph에 입력을 받아올 때 이를 고려해야 한다. u를 앞의 노드, w를 뒤의 노드라고 해보면,
let graph = [...Array(N + 1)].map(() => []);
for (let [u, w] of nodes) {
// 앞의 노드의 인덱스 배열에 뒤의 노드 push
graph[u].push(w);
// 뒤의 노드의 인덱스 배열에 앞의 노드 push(if문 걸어서 중복 되지 않도록 함)
if (!graph[w].includes(u)) {
graph[w].push(u);
}
}
// 매번 값이 작은 노드부터 탐색해야 하므로 원소들을 오름차순 정렬
graph.forEach((el) => el.sort((a, b) => a - b));이렇게 받아오면 양방향 간선일 때도 graph를 받아올 수 있다.
우선 bfs가 좀 더 간단하기 때문에 bfs 함수부터 살펴보자.
BFS
function bfs() {
// graph 입력 받아오는 부분
let graph = [...Array(N + 1)].map(() => []);
for (let [u, w] of nodes) {
graph[u].push(w);
if (!graph[w].includes(u)) {
graph[w].push(u);
}
}
graph.forEach((el) => el.sort((a, b) => a - b));
let visited = [];
let queue = [V];
// while문으로 너비 우선 탐색
while (queue.length) {
// 앞의 노드부터 꺼내온다. (FIFO)
let currentNode = queue.shift();
// 아직 방문 처리 안됐다면 방문 처리
if (!visited.includes(currentNode)) {
visited.push(currentNode);
}
// 현재 노드의 인접 노드들을 순회하면서
for (let nextNode of graph[currentNode]) {
// 아직 방문 안 한 노드들만 queue에 push 한다.
if (!visited.includes(nextNode)) {
queue.push(nextNode);
}
}
}
return visited;
}
// 공백을 간격으로 출력
console.log(bfs().join(" "));bfs는 선입선출인 거 아시쥬??~~~
현재 노드의 인접 노드들을 순회하면서 각각 방문 처리(아직 안 됐을 경우만) 해주면 된다.
다음으로 조금 더 어려웠던 dfs 함수를 살펴보자.
DFS
function dfs() {
// graph 입력 받아오는 부분
let graph = [...Array(N + 1)].map(() => []);
for (let [u, w] of nodes) {
graph[u].push(w);
if (!graph[w].includes(u)) {
graph[w].push(u);
}
}
// 🌟🌟🌟🌟🌟값이 큰 노드부터 push해야만 값이 작은 노드부터 pop해올 수 있으므로 내림차순 정렬 한다.
graph.forEach((el) => el.sort((a, b) => b - a));
let visited = [];
let stack = [V];
// while문으로 깊이 우선 탐색
while (stack.length) {
// 뒤의 노드부터 꺼내온다. (LIFO) 이 때 값이 큰 노드부터 push했으므로 값이 작은 노드부터 나온다.
let currentNode = stack.pop();
// 아직 방문 처리 안됐다면 방문 처리
if (!visited.includes(currentNode)) {
visited.push(currentNode);
}
// 값이 큰 노드부터 순회하며 stack에 push해준다.
for (let nextNode of graph[currentNode]) {
if (!visited.includes(nextNode)) {
stack.push(nextNode);
}
}
}
return visited;
}
console.log(dfs().join(" "));dfs는 후입선출인 거 아시쥬???
다만 처음에 좀 어려웠던 부분은 인접 노드를 순회할 때 값이 큰 노드부터 stack에 push해야 하는 점이었다. 값이 큰 노드부터 push해야만, stack에서 currentNode를 꺼내올 때 값이 작은 노드부터 꺼내올 수 있다. 이 부분을 잘 기억하자!!
이 아이디어는 오늘 코플릿 문제를 풀면서 얻을 수 있었다.
오늘은 2023년 8월 24일.
파이썬으로 다시 풀어봤다.
그런데 graph를 생성하는 과정에서 실수를 했다.
graph = [[] for _ in range(n + 1)]
edges = [list(map(int, s.readline().split())) for _ in range(m)]
# 👿 이렇게 graph 생성 전에 먼저 정렬을 시도했다가 틀렸다.
# edges.sort(key=lambda x: (x[0], x[1]))
for _ in range(m):
[a, b] = edges.pop(0)
graph[a].append(b)
graph[b].append(a)
# 이렇게 graph 생성 후에 정렬해야 한다.
# for el in graph:
# el.sort()반례가 있다.
1 3
2 1만약 이런 입력이 들어온다면,
정렬을 미리했을 때 [1, 3], [2, 1]
이렇게 edges가 정렬될 것이고,
graph = [[], [3, 2], [1], [1]]
이런 결과가 나와서
1번 노드의 인접노드들이 오름차순 정렬되지 않는다.
그리고 또 중요한 한가지!
graph[current_node][::-1]
이건 파이썬에서 리스트를 얕은 복사할 때 사용할 수 있으니 앞으로도 자주 사용하겠다.
코플릿 문제도 잠시 리뷰해보자.
[코플릿 treeDFS]문제
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
입력
인자 1 : node
'value', 'children' 속성을 갖는 객체 (Node)
'node.value'는 number 타입
'node.children'은 Node를 요소로 갖는 배열
출력
배열을 리턴해야 합니다.
주의사항
생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.
입출력 예시
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = dfs(root);
console.log(output); // --> [1, 2, 4, 6, 5, 3, 7]나의 코드
let dfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let stack = [node];
let visited = [];
while (stack.length) {
let currNode = stack.pop();
visited.push(currNode.value);
// 자식 노드들을 역순으로 push함.(stack에서 숫자가 작은 노드가 먼저 pop되어야 하므로)
for (let i = currNode.children.length - 1; i >= 0; i--) {
stack.push(currNode.children[i]);
}
}
return visited;
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};오늘 코플릿 문제도 위의 BFS와 논리는 비슷하다. 트리여서 양방향이 아니라 단방향이라는 점과, node가 객체로 이루어져 있다는 점에서 차이가 있기는 하다. 그런데 문제를 처음 이해할 때 좀 시간이 걸렸다. tree에서 임의의 노드가 들어온다는 건데 그럼 tree가 어찌 생겼는지는 어떻게 알지?;;; <- 이 생각으로 거의 30분 헤맸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
바로 인자로 들어오는 node의 children 배열에 자식 노드들이 들어있는 것이었다...
그리고 인자로 들어오는 임의의 node는 깊이 우선 탐색을 할 때 어차피 루트 노드여야 하므로 조상 노드는 고려할 필요가 없었다.
여하튼 DFS 문제이기 때문에 후입선출이고, stack에 push할 때 역순으로 넣어야 한다는 점이 가장 중요하다.
오늘의 DFS/BFS 공부는 여기서 마무리..를 할까말까 고민 중이다. 좀 더 풀어볼 문제가 있는지 구경 가야지 짜이찌앤~~~
