백준 16964 < DFS 스페셜 저지 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

 

📍알고리즘 분류

- 자료구조

- 그래프 이론

- 그래프 탐색

- 깊이 우선 탐색

 

📍문제 풀이

인접 리스트를 만들 수 있는 정보와, 경로가 주어질 때, 주어진 경로가 DFS를 만족하는 경로인지 확인하라

 

📍의사 코드

경로의 현재 값을 A, 다음 값을 B라고 할 때,

1️⃣주어진 경로를 순회하며, A 와 B를 비교하는 반복문을 만든다

2️⃣분기

- A의 이웃 중에 B가 있으면 continue

- 아닌 경우, A의 이웃 중에 방문 이력이 없는 노드가 존재하면 DFS 경로가 아님

/*
아래 그래프 형태일 때,

1 - 2
|     \
3      4

경로가 1 2 3 4 라면,
      ---
      OK
        ---
        NG -> 2의 이웃중 3이 방문 이력이 없는 정점이므로
 */

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = +in1;
const path = in2.pop().split(" ").map(Number);
const data = in2.map((el) => el.split(" ").map(Number));

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(num) {
    for (let i = 1; i <= num; i++) {
      this.adjacencyList[i] = [];
    }
  }
  addEdge(data) {
    data.map((edge) => {
      this.adjacencyList[edge[0]].push(edge[1]);
      this.adjacencyList[edge[1]].push(edge[0]);
    });
  }
  dfs(path) {
    let answer = 1;
    if (path[0] !== 1) answer = 0;
    const isVisited = {};
    for (let i = 0; i < path.length - 1; i++) {
      isVisited[path[i]] = true;
      if (this.adjacencyList[path[i]].includes(path[i + 1])) continue;
      this.adjacencyList[path[i]].forEach((neighbor) => {
        if (!isVisited[neighbor]) answer = 0;
      });
    }
    return answer;
  }
}

const g = new Graph();
g.addVertex(N);
g.addEdge(data);

console.log(g.dfs(path));

 

📍리팩토링

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = +in1;
const path = in2.pop().split(" ").map(Number);
const data = in2.map((el) => el.split(" ").map(Number));

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(num) {
    for (let i = 1; i <= num; i++) {
      this.adjacencyList[i] = [];
    }
  }
  addEdge(data) {
    data.map((edge) => {
      this.adjacencyList[edge[0]].push(edge[1]);
      this.adjacencyList[edge[1]].push(edge[0]);
    });
  }
  dfs(path) {
    if (path[0] !== 1) return 0;
    const isVisited = {};
    for (let i = 0; i < path.length - 1; i++) {
      isVisited[path[i]] = true;
      if (this.adjacencyList[path[i]].includes(path[i + 1])) continue;
      for (let neighbor of this.adjacencyList[path[i]]) {
        if (!isVisited[neighbor]) return 0; // 바로 종료
      }
    }
    return 1;
  }
}

const g = new Graph();
g.addVertex(N);
g.addEdge(data);

console.log(g.dfs(path));

 

0을 리턴하고 바로 종료하게 작성하여 시간복잡도를 줄이려 했으나, 오히려 시간 복잡도가 16ms 증가했다 (무의미)

게다가 메모리도 10MB 정도 더 씀..