[boj 13023] ABCDE -js

DFS & BFS (동빈나)

먼저 dfs 를 다시 학습하고 구현을 해보았다. dfs를 구현하는 방법은 재귀혹은 스택 자료구조를 이용한다. 

// dfs

// 노드 연결 정보
const graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
];

const visited = new Array(9).fill(false);

const dfs = (graph, node, visited) =>{
    visited[node] = true; // 방문함
    console.log(node);
    for(const n of graph[node]){
        !visited[n] ? dfs(graph, n, visited) : null;
    }
}

dfs(graph, 1, visited);

 

 

먼저 해당 문제는 A-B-C-D 이런 식으로 연결된 노드를 탐색하면 1을 출력하면 되는 문제이다.

1. 주어지는 관계들을 그래프로 생성

2. 주고 이를 dfs 를 활용해 탐색

3. 이때 연속된 노드들의 개수가 4인지 탐색한다.

4. 또, 모든 노드들에서 시작해 탐색한다.

// ABCDE

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

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

const sol = (N, M, arr) =>{
    const graph = Array.from(Array(N), () => new Array());
    let isSuccess = false;

    while(arr.length){
        const index1 = arr.shift();
        const index2 = arr.shift();
        graph[index1].push(index2);
        graph[index2].push(index1);
    }
    
    const visited = new Array(N).fill(false);

    const dfs = (v, cnt) => {
        if (cnt >= 4){
            isSuccess = true;
            return;
        }
        // console.log(`v:${v}, cnt:${cnt}`);
        visited[v] = true;
        for(const node of graph[v]){
            !visited[node] ? dfs(node, cnt+1) : null;
            if(isSuccess){
                return;
            }
        }
        visited[v] = false;
    }

    for(let i=0; i<N; i++){
        dfs(i,0);
        if(isSuccess) break;
    }
    isSuccess ? console.log(1) : console.log(0);
}



sol(N, M, arr);

더 능숙해질때 까지 연습하자..