문제

그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다.

단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다.
단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다.
이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다.

트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프
트리의 정보와 질의가 주어질 때, 질의에 대한 답을 하시오.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정보 a, b가 주어진다. 이는 a정점과 b정점이 연결되어 있다는 뜻이며, 입력으로 주어지는 정보는 트리임이 보장된다. (1 ≤ a, b ≤ N)

다음 줄에는 질의의 개수 q가 주어진다. (1 ≤ q ≤ 100,000) 다음 q줄에는 질의 t k가 주어진다. (1 ≤ t ≤ 2) t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다. t가 1일 때는 (1 ≤ k ≤ n)이며, t가 2일 때는 (1 ≤ k ≤ n - 1)이다.

출력

프로그램의 출력은 표준 출력으로 한다. q줄에 대하여 해당 질의에 대한 답을 한다. 각각은 개행으로 구분하며, 질의가 맞다면 ‘yes’를, 질의가 틀리면 ‘no’를 출력한다.

예제 입력

5
1 2
2 3
3 4
4 5
4
1 1
1 2
2 1
2 2

예제 출력

no
yes
yes
yes

내가 했던 풀이

항상 트리만 입력됨이 보장되기 때문에 트리의 특징을 생각해주면 단절점과 단절선을 찾는 로직을 구현하지 않아도 된다.
트리는 사이클이 존재하지 않기 때문에 그래프가 2개 이상으로 나뉘는 경우는 하나의 노드가 자식 노드를 2개 이상 가지고 있을 때이다. 즉, 하나의 노드에서 연결되어 있는 노드가 2개 이상일 경우에는 항상 단절점이다. 또한 같은 이유로 트리의 모든 간선을 제거하면 항상 그래프가 2개 이상으로 나뉘게 된다. 그러므로 트리의 모든 간선은 항상 단절선이다.

코드

const fs = require('fs');
let input = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let index = 1;
let N = Number(input[0]);
let graph = Array.from({ length: N + 1 }, () => []);
let info = [];
for (let i = 0; i < N - 1; i++) {
  let [a, b] = input[index++].trim().split(' ').map(Number);
  info.push([a, b]);
  graph[a].push(b);
  graph[b].push(a);
}
let q = Number(input[index++]);

let answer = '';
for (let i = 0; i < q; i++) {
  let [t, k] = input[index++].trim().split(' ').map(Number);
  if (t === 1) {
    if (graph[k].length >= 2) answer += 'yes' + '\n';
    else answer += 'no' + '\n';
  } else {
    answer += 'yes' + '\n';
  }
}

console.log(answer.trim());

회고

당연히 입력 값이 크기 때문에 단절점과 단절선을 각각 구해주는 로직을 구현했으나 시간초과가 되었고 DFS로 풀이를 했는데 트리의 특성만 이용하면 DFS도 신경쓰지 않아도 된다는 풀이를 참고하니 풀이가 간단하고 훨씬 이해가 쉬웠다. 트리만 입력된다 했을 때 트리에 집중했다면 생각했을 법한 풀이였는데 문제를 분석할 줄 알아야... 할 것 같다