[Silver I] 단절점과 단절선 - 14675
성능 요약
메모리: 57668 KB, 시간: 404 ms
분류
단절점과 단절선, 그래프 이론, 트리
제출 일자
2024년 1월 16일 21:03:54
문제 설명
그래프 이론에서 단절점(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’를 출력한다.
접근 방법
문제를 해결하기전에 입력으로 주어지는 정보는 트리임이 보장된다는 것과 단절점과 단절선에 대해서 먼저 알고 시작하면 좋다.
단절점
트리에서 노드를 삭제했을 때 그래프가 나누어지지않는, 즉 그래프가 나누어지지 않는 노드는 무조건 리프노드이다.
-> 자식을 가지고 있는 노드라면 해당 노드를 제거시 무조건 그래프가 형성되기 때문이다.
단절선
트리에서는 어떤 노드에 대한 간선을 지우더라도 그래프가 두개이상으로 형성이 된다.
-> 자식노드가 없는 리프노드를 생각해보면 부모노드와 자식노드가 분리된다.
즉, 우리는 단절점에 연결된 노드의 개수가 1개라면(리프 노드라면) 단절점으로 보지않고 어떠한 노드를 끊어도 단절선이라는 것을 알 수 있다.
풀이 코드
그러한 접근 방법으로 쉽게 해결 가능하다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
// 노드의 개수 n
int n = Integer.parseInt(br.readLine());
// 노드의 개수당 연결된 노드를 즉, 간선을 세어주기 위한 배열 생성
int[] nodes = new int[n + 1];
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
// 연결된 노드의 간선의 개수를 더해줌
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
nodes[a]++;
nodes[b]++;
}
// 질의의 개수를 입력 받는다.
int q = Integer.parseInt(br.readLine());
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
// 질문이 단절선에 대한 질문이라면 무조건 yes
if (t == 2) {
sb.append("yes");
}
// 단절점에 대한 질문일 때 해당 노드의 간선의 개수가 1개라면(리프 노드라면) 단절점이 아니다.
else if (nodes[k] == 1){
sb.append("no");
}
// 노드의 간선의 개수가 1개 이상이라면(트리임이 보장되기에 0개 일 수 없다.) 단절점이다.
else{
sb.append("yes");
}
sb.append("\n");
}
System.out.println(sb);
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 1389번 : 케빈 베이컨의 6단계 법칙 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |
---|---|
[백준] 11403번 : 경로 찾기 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |
[백준] 9934번 : 완전 이진 트리 Silver1(실버1) - JAVA[자바] (1) | 2024.01.15 |
[백준] 18429번 : 근손실 Silver3(실버3) - JAVA[자바] (0) | 2024.01.15 |
[백준] 1935번 : 후위 표기식2 Silver3(실버3) - JAVA[자바] (1) | 2024.01.14 |