글 읽기 - 1766 문제집 node.js 런타임에러가 나는지 모르겠습니다... 도와주세요!!

yeum0523 2년 전 0

위상 정렬 개념을 사용해야 한다고 하길래 위상 정렬과 최소힙을 사용해서 구현했습니다.

제출시, 87%에서 런타임에러가 나는데 제가 어디에서 실수를 하였는지 잘 모르겠네요..

부족한점 지적해주면 감사하겠습니다!

감사합니다 :)

class Heap {
    constructor() {
        this.heap = [null];
        this._size = 0;
        this.operator = function (a, b) { return a < b; };
    }
    size() {
        return this._size;
    }
    // 힙 push
    push(x) {
        this.heap[++this._size] = x;
        for (var cur = this._size; cur > 1; cur >>= 1) {
            var half = cur >> 1;
            if (this.operator(this.heap[cur], this.heap[half])) {
                var temp = this.heap[cur];
                this.heap[cur] = this.heap[half];
                this.heap[half] = temp;
            }
            else {
                break;
            }
        }
    }
    // 힙 pop
    pop() {
        if (this._size === 0)
            return;
        const returnVal = this.heap[1];
        this.heap[1] = this.heap[this._size--];
        var child;
        for (var cur = 1; (cur << 1) <= this._size; cur = child) {
            var dC = cur << 1;
            if (dC + 1 > this._size || this.operator(this.heap[dC], this.heap[dC + 1])) {
                child = dC;
            }
            else {
                child = dC + 1;
            }
            if (this.operator(this.heap[child], this.heap[cur])) {
                var temp = this.heap[cur];
                this.heap[cur] = this.heap[child];
                this.heap[child] = temp;
            }
            else {
                break;
            }
        }
        return returnVal;
    }
}




const [num, ...no] = require('fs').readFileSync(__dirname + '/dev/stdin').toString().trim().split('\n');
const [numProblem, problemInfo] = num.split(' ').map(i => parseInt(i));
const node = no.map(i => i.split(' ').map(j => parseInt(j)));
const heap = new Heap();
// 연결된 간선의 갯수를 저장하는 배열입니다.
const indegree = new Array(numProblem + 1).fill(0);
// 노드의 연결 관계를 나타내는 배열입니다.
const array = new Array(numProblem + 1).fill(null);
const answer = [];

for (let i = 1; i <= problemInfo; i++) {
    const [x, y] = node[i - 1];

    if (!array[x]) array[x] = [];
    if (!array[y]) array[y] = [];
    // 먼저 풀어야 하는 문제 기준으로 이후에 푸는 문제를 구성합니다.
    // ex) 3 -> [1], 4 -> [2]
    array[x].push(y);
    // 이후에 풀어야하는 문제는 먼저 풀어야하는 노드와 연결했기 때문에 간선의 갯수를 카운팅합니다.
    indegree[y] += 1;
}
// 출발 노드를 체크해, 해당 노드를 힙에 넣습니다.
for (let i = 1; i <= numProblem; i++) if (indegree[i] === 0) heap.push(i);

// 모든 노드를 방문할 때 까지
while (heap.size() ) {
    // 힙에 있는 출발 노드를 뽑아냅니다.
    const node = heap.pop();
    answer.push(node);
    // 해당 노드와 연결되어 있는 노드의 간선을 삭제합니다.
    for (let i = 1, length = array[node].length; i <= length; i++) {
        const idx = array[node][i - 1];
        // 연결되어있는 출발 노드가 pop되었기 때문에 해당 간선을 삭제합니다.
        indegree[idx] -= 1;
        // 삭제하였더니, 해당 노드가 출발 노드가 되었다면 힙에 넣습니다.
        if (indegree[idx] === 0) heap.push(idx);
    }
}

console.log(answer.join(' '));

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

문제

문제

출처

ICPC

1766 문제집 node.js 런타임에러가 나는지 모르겠습니다... 도와주세요!!

yeum0523 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말