글 읽기 - 출력 초과 질문입니다.

hant422 2년 전 0

Javascript 특성상 dfs를 재귀로 구현하면 stack overflow가 발생하기 때문에, 유사 Call Stack을 구현해서 풀었습니다. (원본 재귀 dfs 함수도 주석으로 넣어놨습니다.)

하지만 이제는 stack overflow 대신에 이유를 모르는 출력 초과가 발생합니다.

틀렸습니다, 메모리 초과, 시간 초과가 아닌 출력 초과 떄문에 고생하는 것은 처음이라 많이 당황스럽습니다.

어떤게 잘못된 걸까요? 고수님들의 조언이 절실합니다 ㅜㅜ

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

const [V, E] = input[0].split(" ").map(Number);
const edges = input.slice(1, V + 1).map((str) => str.split(" ").map(Number));

const con = Array.from({ length: V + 1 }, () => []);
const orders = Array(V + 1);
const singles = new Set();
let order = 1;

edges.forEach(([node1, node2]) => {
  con[node1].push(node2);
  con[node2].push(node1);
});

/* 재귀로 구현한 DFS */
// const dfs = (node) => {
//   let low = order++;
//   orders[node] = low;

//   con[node].forEach((next) => {
//     if (orders[next]) {
//       low = Math.min(low, orders[next]);
//     } else {
//       const nextLow = dfs(next);
//       if (nextLow >= orders[node]) singles.add(node);
//       else low = Math.min(low, nextLow);
//     }
//   });

//   return low;
// };

/* 유사 Callstack을 구현해 Loop로 구현한 DFS */
const dfs = (start) => {
  orders[start] = order++;
  const callStack = [[start, -1, orders[start]]];
  let returnValue = null;

  while (callStack.length) {
    let [node, index, low] = callStack.pop();
    const nextCnt = con[node].length;

    if (returnValue) {
      if (returnValue >= orders[node]) singles.add(node);
      else low = Math.min(low, returnValue);
      returnValue = null;
    }

    let nextIndex = index + 1;
    let nextNode = con[node][nextIndex];

    while (nextIndex < nextCnt && orders[nextNode]) {
      low = Math.min(low, orders[nextNode]);
      nextIndex += 1;
      nextNode = con[node][nextIndex];
    }

    if (nextIndex === nextCnt) {
      returnValue = low;
    } else {
      orders[nextNode] = order++;
      callStack.push([node, nextIndex, low]);
      callStack.push([nextNode, -1, orders[nextNode]]);
    }
  }
};

for (let root = 1; root <= V; root += 1) {
  if (orders[root]) continue;
  orders[root] = order++;
  let childCnt = 0;

  con[root].forEach((node) => {
    if (orders[node]) return;
    dfs(node);
    childCnt += 1;
  });

  if (childCnt >= 2) singles.add(root);
}

const ans = Array.from(singles).sort((a, b) => a - b);
console.log(`${ans.length}\n${ans.join(" ")}`.trim());

djs100201 2년 전 0

출력초과는 틀렸습니다랑 유사합니다. 정답보다 많은 답을 출력한 것입니다.

hant422 2년 전 0

맞습니다. 틀력습니다 중에서도 단절점이 0개여서 두번째 줄이 출력되지 않아야 하는데, 두번째 줄을 출력하면 나오는 현상이였습니다.

단순 오타였습니다. Edge 입력값을 E만큼 받아야 하는데, 무슨 생각이였는지 V만큼 받은게 원인이였습니다. 이걸로 3시간이 넘게 고민했는데 너무 허무하네요 ㅜㅜ

const edges = input.slice(1, E + 1).map((str) => str.split(" ").map(Number));

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

문제

문제

출처

ICPC

출력 초과 질문입니다.

hant422 2년 전 0

djs100201 2년 전 0

hant422 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말