글 읽기 - 정답은 맞췄는데 속도 차이가 왜 나는지 궁금해서 질문드립니다.

kown9512 3년 전 0

소스코드 34, 37 조건문에 flag 를 적고 안 적고에 따라 속도가 차이납니다.

동일 코드 테스트 별 오차는 4ms 정도로 알고있는데,

flag 를 넣으면 20 ms 빨라지고, 안 넣으면 넣은 것 보다 20ms 느립니다.

왜 그런 건지 혹시 설명해주실 수 있을까요???

'use strict';

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(v => v.trimEnd());

let output = '';
const solution = (input) => {
  const stationNum = +input[0];
  const list = Array.from({length : stationNum + 1}, () => Array());
  const visited = Array(stationNum + 1).fill(-1);
  for (let i = 1; i < input.length; i++) {
    const [a, b] = input[i].split(' ');
    list[+a].push(+b);
    list[+b].push(+a);
  }

  let flag = false;
  let loopDeps = 0;
  let loopStaion = 0;
  // 순환선 찾기.
  const dfs = (curStation, deps = 0) => {
    if (visited[curStation] === -1) visited[curStation] = 0;

    for (let i = 0; i < list[curStation].length; i++) {
      if (flag) break;
      const nextStation = list[curStation][i];
      if (visited[nextStation] === -1) {
        visited[nextStation] = visited[curStation] + 1;
        dfs(nextStation, deps + 1);
        if (!flag) {
          visited[nextStation] = -1;
          // 순환선을 찾았고 다음역의 깊이가 순환선 시작점보다 깊다면 0을 할당한다.
        } else if (flag && visited[nextStation] >= loopDeps) {
          visited[nextStation] = 0;
          // 순환선을 찾았고 다음 역의 깊이가 순환선의 시작점보다 얕다면 미방문 처리한다.
        } else if (flag && visited[nextStation] < loopDeps) {
          visited[nextStation] = -1;
        }
      }
      // 순환선을 찾았으면 찾은 다음 역을 순환선의 시작점으로 간주하고 깊이와 역 번호를 기록한다.
      else if (visited[curStation] - 2 >= visited[nextStation]) {
        flag = true;
        loopDeps = visited[nextStation];
        loopStaion = nextStation;
      }
    }
    if (curStation !== loopStaion && deps === 0) visited[curStation] = -1;
  }

  const bfs = (loopLineSt, que = [loopLineSt]) => {
    
    while (que.length) {
      const curStation = que.shift();
      for (let i = 0; i < list[curStation].length; i++) {
        const nextStation = list[curStation][i];
        if (visited[nextStation] === -1) {
          visited[nextStation] = visited[curStation] + 1;
          que.push(nextStation);
        }
      }
    }

  }

  for (let i = 1; i <= stationNum; i++) {
    if (visited[i] === -1) {
      dfs(i);
      if (!flag) {
        visited[i] = -1;
      } else if (flag) {
        break;
      }
    }
  }

  for (let i = 1; i < list.length; i++) {
    for (let j = 0; j < list[i].length; j++) {
      const mainBranch = i;
      const sideBranch = list[i][j];
      if (visited[mainBranch] === 0 && visited[sideBranch] === -1) {
        bfs(mainBranch);
      }
    }
  }

  output = visited.slice(1);
}

solution(input)
// console.log(output.join(' '));

fs.writeFileSync('/dev/stdout', output.join(' '));

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정답은 맞췄는데 속도 차이가 왜 나는지 궁금해서 질문드립니다.

kown9512 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말