백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 24479 , 알고리즘 수업 - 깊이 우선 탐색 1

백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 24479 , 알고리즘 수업 - 깊이 우선 탐색 1

 

 

 

문제 출처

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

 

 

 

 

시간 초과가 난 문제이다.

 

파이썬에서는 시간 초과가 안나는 로직인데 자바스크립트에서는 시간초과가 난다.

 

shift 가 O(N) 복잡도를 가져서 shift 를 빼고 코드를 작성했지만 여전히 시간초과...

 

그래도 예제나 반례는 모두 맞고 파이썬으로도 똑같은 로직으로 통과했으니 

 

DFS 를 JS 코드로 짜는 법정도만 참고하길 바란다.

 

 

 

 

 

 

풀이법

 

*시간 초과 발생

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let cnt = 1;
const BFS = (start) => {
  for (i of graph[start]) {
    if (!visited[i]) {
      cnt += 1;
      visited[i] = true;
      cntArr[i] = cnt;
      BFS(i);
    }
  }
  return;
};

const [X, Y, Z] = input[0].split(" ").map(Number);
const graph = [...new Array(X + 1)].map(() => []);
const visited = [...new Array(X + 1)].fill(false);
const cntArr = [...new Array(X + 1)].fill(Number(0));
visited[Z] = true;
cntArr[Z] = 1;

for (let i = 1; i < Y + 1; i++) {
  const [a, b] = input[i].split(" ").map(Number);
  graph[a].push(b);
  graph[b].push(a);
}

for (let j = 0; j < X; j++) {
  graph[j].sort((a, b) => a - b);
}

BFS(Z, 2);

for (let k = 1; k < X + 1; k++) {
  console.log(cntArr[k]);
}