[boj 1260] DFS와 BFS -js

문제를 제대로 읽지않아 조건인 정점 번호가 작은 것을 먼저 방문한다는 것을고려하지 않아 헤맸다.

 

문제 좀 잘 읽자!!!

// DFS와 BFS 

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split(/\s/).map(Number);

const [N, M, V, arr] = [parseInt(input.shift()), parseInt(input.shift()), parseInt(input.shift()), [...input]];

const sol = (N, M, V, arr) =>{
    const graph = Array.from(Array(N+1), ()=>new Array());
    const visited_dfs = new Array(N+1).fill(false);
    const result_dfs = [];
    while(arr.length){
        const node1 = arr.shift();
        const node2 = arr.shift();
        graph[node1].push(node2);
        graph[node2].push(node1);
    }
    
    for(let i=0; i<graph.length; i++){
        graph[i].sort((a,b) => a-b);
    }

    const dfs = (v) =>{
        visited_dfs[v] = true;
        result_dfs.push(v);
        for(const node of graph[v]){
            !visited_dfs[node] ? dfs(node) : null;
        }
    }

    const bfs = (v) =>{
        const visited = [];
        let needVisit = [];

        needVisit.push(v);

        while(needVisit.length){
            const node = needVisit.shift();
            if(!visited.includes(node)){
                visited.push(node);
                needVisit = [...needVisit, ...graph[node]];
            }
        }
        return visited;
    }

    dfs(V);

    console.log(result_dfs.join(' '));
    console.log((bfs(V)).join(' '));
}

sol(N, M, V, arr);

DFS => 스택 or 재귀

BFS => 큐

 

DFS

1. 방문을 표시할 배열 생성

2. dfs 함수 구현 및 방문 노드 표시

3. 해당 노드의 자식노드들이 방문하지 않았다면 dfs재귀 호출로 해당 노드 탐색!

 

BFS

1. bfs 함수 구현 및 방문할 노드배열에 푸시

2. 방문할 노드에서 shift()로 하나씩 꺼내어 방문했는지 확인

3. 안했따면 방문함 배열에 푸시, 기존의 방문할 노드 뒤에 현재 방문한 노드의 자식노드들을 추가!

4. 방문할 노드가 없을 때까지 반복한다.