[JavaScript] 백준 1260 DFS와 BFS (JS)

문제 링크

문제 설명

간략한 깊이 우선 탐색과 깊이 우선 탐색 문제이다.
입력 받은 값을 DFS, BFS순으로 출력을 하면 되는 문제였다.
입력은 첫줄에 " 노드 수, 간선 수, 시작 노드 "이며 그 후에는 연결 관계가 주어진다.

풀이 과정

고려할 점
1. DFS는 재귀를 사용하여 구현한다.
2. BFS는 Queue(큐)와 반복문을 사용하여 구현한다.
따라서 DFS와 BFS 각각 재귀를 어떻게 사용할지, 큐와 반복문을 어떻게 사용할지 고민하며 코드 작성을 하면 된다.

그럼 입력부터 순서대로 생각을 해보자.

• 입력에서 N * M의 행렬이나 map이 주어지는 문제가 아니다.
• 입력에서 연결 관계를 리스트 느낌으로 주고 있다.
• 그렇다면 입력을 인접 리스트로 저장한다.

입력 값 저장

    let fs = require("fs");
    let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
    let [N, Bridge, Start] = input.shift().split(" ").map(Number);
    let trees = new Array(N).fill(0).map(_ => []);
    for (let i = 0; i < Bridge; i++) {
        let node = input[i].split(" ").map(Number);
        trees[node[0] - 1].push(node[1]);
        trees[node[1] - 1].push(node[0]);
    }

DFS(깊이 우선 탐색) 함수 코드

    let DFSVisited = new Array(N).fill(false);
    let DfsAnswer = [];
    const DFS = (now) => {
      	// visited 배열 체크 후 변경, 정답 배열에 push
        if (!DFSVisited[now - 1]) {
            DFSVisited[now - 1] = true;
            DfsAnswer.push(now);
        }
      	// 반복문을 돌며 visited가 true면 넘어가고 아니면 재귀
        for (let i = 0; i < trees[now - 1].length; i++) {
            if (DFSVisited[trees[now - 1][i] - 1]) continue;
            DFS(trees[now - 1][i]);

        }
    };

    DFS(Start);

BFS(너비 우선 탐색) 함수 코드

    let BFSVisited = new Array(N).fill(false);
    let BfsAnswer = [];
    const BFS = (now) => {
        let queue = [now];
        while (queue.length) {
            let Position = queue.shift();
          	// visited 가 ture면 넘어감
            if (BFSVisited[Position - 1]) continue;
          	// visited 가 false면 ture로 바꿔주고 정답 배열에 push
            BFSVisited[Position - 1] = true;
            BfsAnswer.push(Position);
          	
            for (let i = 0; i < trees[Position - 1].length; i++) {
                if (!BFSVisited[trees[Position - 1][i] - 1]) {
                    queue.push(trees[Position - 1][i]);
                }
            }
        }
    };
    BFS(Start);

그런데 여기서 이대로 제출을 하면 틀렸다고 나오게 된다.
여기서 문제는 인접 리스트로 저장을 했을 때 입력 값이 작은 순서대로 차례로 입력을 받는게 아니다.
그러면 입력 받는 연결 관계의 순서에 따라 탐색 순서가 바뀌게 된다.
따라서 인접 리스트로 인덱스 번호를 저장하고 해당 값을 sort()를 이용하여 정렬해야 한다.

정렬 코드

trees.forEach(v => v.sort((a, b) => a - b));

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
    let [N, Bridge, Start] = input.shift().split(" ").map(Number);
    let trees = new Array(N).fill(0).map(_ => []);
    trees.forEach(v => v.sort((a, b) => a - b));
    for (let i = 0; i < Bridge; i++) {
        let node = input[i].split(" ").map(Number);
        trees[node[0] - 1].push(node[1]);
        trees[node[1] - 1].push(node[0]);
    }
    trees.forEach(v => v.sort((a, b) => a - b));

    let BFSVisited = new Array(N).fill(false);
    let BfsAnswer = [];
    const BFS = (now) => {
        let queue = [now];

        while (queue.length) {
            let Position = queue.shift();
            if (BFSVisited[Position - 1]) continue;
            BFSVisited[Position - 1] = true;
            BfsAnswer.push(Position);
            for (let i = 0; i < trees[Position - 1].length; i++) {
                if (!BFSVisited[trees[Position - 1][i] - 1]) {
                    queue.push(trees[Position - 1][i]);
                }
            }
        }
    };
    BFS(Start);

    let DFSVisited = new Array(N).fill(false);
    let DfsAnswer = [];
    const DFS = (now) => {
        if (!DFSVisited[now - 1]) {
            DFSVisited[now - 1] = true;
            DfsAnswer.push(now);
        }
        for (let i = 0; i < trees[now - 1].length; i++) {
            if (DFSVisited[trees[now - 1][i] - 1]) continue;
            DFS(trees[now - 1][i]);

        }
    };

    DFS(Start);
	console.log(`${DfsAnswer.join(" ")}\n${BfsAnswer.join(" ")}`);

후기

마지막 정렬을 해줘야하는 부분 때문에 오래 걸리게 되었다.
그리고 재귀를 사용하다가 스택 오버가 되어서 수정했다.
아직 재귀를 사용하는 DFS가 익숙하지 않은 것 같다.