문제

풀이

단순히 DFS와 BFS의 개념을 알고 있는지와 입력 받은 여러줄의 문자열을 잘 가공해서 사용할 수 있는지를 물어보는 문제라고 느껴졌다.

입력 받은 노드간의 연결을 이중 배열에 넣어서 배열의 인덱스마다 양방향 노드의 도착 노드의 값을 넣어서 자료에 접근할 수 있도록 만들었다.

[[], [2,3,4], [1,4], [1,4], [1,2,3]]

이런식으로 이중 배열을 만들어 사용하도록 구현했다.

코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");
const [n, m, v] = input[0].split(" ").map(Number);
let graph = Array.from({length: n + 1}, () => new Array());

for (let i = 0; i < m; i++) {
    let [start, end] = input[i + 1].split(" ").map(Number);
    graph[start].push(end);
    graph[end].push(start);
}

graph.forEach((element) => {
    element.sort((a, b) => a - b);
});

let visited = new Array(n + 1).fill(0);
let answer_dfs = [];

function DFS(v) {
    if (visited[v] === 1) {
        return;
    }
    answer_dfs.push(v);
    visited[v] = 1;
    if (answer_dfs.length === n) {
        return answer_dfs;
    } else {
        for (let i = 0; i < graph[v].length; i++) {
            DFS(graph[v][i]);
        }
    }
}

DFS(v);
console.log(answer_dfs.join(" "));

let answer_bfs = [];
visited.fill(0);

function BFS(v) {
    let queue = [v];
    while(queue.length) {
        let nv = queue.shift();
        if (visited[nv] === 1) {
            continue;
        }
        visited[nv] = 1;
        answer_bfs.push(nv);
        for (let i = 0; i < graph[nv].length; i++) {
            let next = graph[nv][i];
            if (visited[next] === 0) {
                queue.push(next);
            }
        }
    }
}

BFS(v);
console.log(answer_bfs.join(" "));