[JavaScript/DFS/BFS] 백준 실버 1 : 1260 - DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

📌 작성한 코드 

// 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;
};

 

---