ABOUT ME

Today
Yesterday
Total
  • [백준/javascript] 1260 DFS와 BFS
    카테고리 없음 2023. 2. 25. 15:00
    const fs = require("fs");
    // let stdin = fs.readFileSync("./input.txt").toString();
    let stdin = fs.readFileSync("/dev/stdin").toString();
    //
    const input = stdin.split("\n").map((v) => v.split(" ").map(Number));
    const [a, ...b] = input;
    // const [N, A, operators] = input;
    const [n, m, v] = [...a];
    
    class Graph {
      constructor() {
        this.adjacentList = {};
      }
      addEdge(v1, v2) {
        if (!this.adjacentList[v1]) {
          this.adjacentList[v1] = [];
        }
        if (!this.adjacentList[v2]) {
          this.adjacentList[v2] = [];
        }
        this.adjacentList[v1].push(v2);
        this.adjacentList[v2].push(v1);
      }
      sort() {
        const adjacentList = this.adjacentList;
        for (let key in adjacentList) {
          adjacentList[key].sort((a, b) => a - b);
        }
      }
      dfs(v) {
        const result = [];
        const visited = {};
        const adjacentList = this.adjacentList;
        function dfsRecurr(v) {
          if (!v) return null;
          visited[v] = true;
          result.push(v);
          if (adjacentList[v]) {//이 if문이 있어야 정점에 간선연결이 되어있지 않은 경우를 대비할 수 있다.
            adjacentList[v].forEach((element) => {
              if (!visited[element]) {
                return dfsRecurr(element);
              }
            });
          }
        }
        dfsRecurr(v);
        return result;
      }
      bfs(v) {
        const queue = [v];
        const result = [];
        const visited = {};
        const adjacentList = this.adjacentList;
        let currentV;
        visited[v] = true;
        while (queue.length !== 0) {
          currentV = queue.shift();
          result.push(currentV);
          if (adjacentList[currentV]) {//정점에 간선연결이 되어있지 않은 경우 대비
            adjacentList[currentV].forEach((el) => {
              if (!visited[el]) {
                visited[el] = true;
                queue.push(el);
              }
            });
          }
        }
        return result;
      }
    }
    
    const graph = new Graph();
    b.map((el) => graph.addEdge(...el));
    graph.sort();
    console.log(graph.dfs(v).join(" "));
    console.log(graph.bfs(v).join(" "));

    어마어마하게 오래 걸린 ㅎㅎ... 이제 DFS와 BFS 열심히 연습하면 된다 ㅎㅎ..

Designed by Tistory.