[백준] 19641 중첩 집합 모델 (Javascript)

문제

BOJ19641_중첩 집합 모델

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1, -1).map((e) => e.split(' ').map(Number));
const root = +input.slice(-1);
const graph = Array.from({ length: N + 1 }, () => []);
arr.forEach(([v, ...row]) => {
    row.splice(-1, 1);
    graph[v] = row.sort((a, b) => a - b);
});
const tree = Array.from({ length: N + 1 }, () => [0, 0]);

let order = 0;
function dfs(cur) {
    tree[cur][0] = ++order;
    for (let next of graph[cur]) {
        if (tree[next][0]) continue;
        dfs(next);
    }
    tree[cur][1] = ++order;
}

dfs(root);
let answer = '';
for (let i = 1; i <= N; i++) {
    answer += `${i} ${tree[i][0]} ${tree[i][1]}\n`;
}
console.log(answer.trimEnd());

풀이

우선 이 문제는 문제 자체가 이해하기 어려워서 다른 분의 블로그를 참고했다.

우선 각 노드에 left와 right에 order가 정해지는 방식은 아래와 같다.

최상위 노드인 HI-ARC 의 left는 1이다.
HI-ARC의 하위 노드인 경영지원실의 left는 2다.
경영지원실의 하위 노드인 사업전략팀의 left는 3이다.
사업전략팀의 하위 노드인 사원1의 left는 4다.
사원1은 하위 노드가 없다. 즉, 말단 노드이므로 right를 5로 설정하고 상위 노드로 이동한다.
사업전략팀의 하위 노드인 사원2의 left는 6이다.
사원2는 말단 노드이므로 right를 7로 설정하고 상위 노드로 이동한다.
사업전략팀의 하위 노드는 전부 탐색했으므로 right를 8로 설정하고 상위 노드로 이동한다.
경영지원실의 하위 노드인 법무팀의 left는 9다.
법무팀의 하위 노드인 사원3의 left는 10이다.
사원3은 말단 노드이므로 right를 11로 설정하고 상위 노드로 이동한다.
법무팀의 하위 노드는 전부 탐색했으므로 right를 12로 설정하고 상위 노드로 이동한다.

.
.
.

이렇게 모든 노드의 left, right를 설정해준 뒤 모든 노드의 노드 번호, left, right 를 출력해주면 되는 문제다.

그럴려면 우선 인접한 노드의 정보를 담을 그래프와 각 노드의 left, right를 저장할 트리를 만들어보자.

// 그래프 초기화
const graph = Array.from({ length: N + 1 }, () => []);
arr.forEach(([v, ...row]) => {
    row.splice(-1, 1);
    graph[v] = row.sort((a, b) => a - b);
});
// 트리 초기화
const tree = Array.from({ length: N + 1 }, () => [0, 0]);

그리고 DFS를 통해 모든 노드를 방문해주며 left와 right를 설정한다.

let order = 0;
function dfs(cur) {
    tree[cur][0] = ++order;
    for (let next of graph[cur]) {
        if (tree[next][0]) continue;
        dfs(next);
    }
    tree[cur][1] = ++order;
}

dfs(root);

order는 계속해서 1씩 증가하니 전역에 선언한다.
그리고 현재 노드와 인접한 노드를 탐색하며 만약 인접 노드의 left가 0이 아니라면 이미 방문한 적 있는 노드라는 뜻이므로 그냥 넘어가고, left가 0이라면 방문해준다.

인접 노드 중 방문한 적 없는 노드가 더이상 없으면 반복문은 종료되고 right가 설정되며 하나의 dfs가 종료된다.

그렇게 모든 노드의 left와 right를 설정해주었으면 이제 이것을 출력해주어야 한다.

let answer = '';
for (let i = 1; i <= N; i++) {
    answer += `${i} ${tree[i][0]} ${tree[i][1]}\n`;
}
console.log(answer.trimEnd());

console.log(), process.stdout.write()은 수행시간이 길기 때문에 이를 반복문 내부에서 사용할 경우 시간 초과가 발생한다.

따라서 answer 변수에 줄바꿈을 포함하여 문자열을 몰아넣고 한번에 출력하는 방식으로 구현했다.