[BOJ] 백준 14675번 단절점과 단절선 (Java)

#14675 단절점과 단절선

난이도 : 골드 5

유형 : 트리 / 그래프 이론

14675번: 단절점과 단절선

▸ 문제

그래프 이론에서 단절점(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’를 출력한다.

 

문제 풀이  

트리로 주어진 데이터에서 정점이 없어질 경우와 간선이 없어질 경우 해당 트리에 어떠한 변화가 생기는지 파악해주면 된다.

 

트리에서 간선이 없어질 경우

간선이 없어지는 경우는 모두 똑같다. 한 정점과 다른 한 정점의 연결이 끊어지기 때문에 당연히 트리는 2개의 그래프로 나눠질 수 밖에 없다.

 

어느 간선을 잘라도 그래프 2개

 

정점이 없어지는 경우

이 또한 연결되어 있는 간선의 갯수로 변화를 파악할 수 있다. 해당 정점이 없어지게 되면 해당 간선의 갯수만큼의 그래프가 생기게 된다.

 

만약 리프노드인 경우는 간선이 1개이므로 없애도 1개의 트리 또는 그래프를 생기게 된다.

간선 1개를 가진 정점을 제거할 경우

 

 

간선이 2개인 정점을 없애는 경우, 2개의 트리 또는 그래프가 생기게 된다. 마찬가지로 3개인 경우에는, 3개의 트리 또는 그래프가 생기는 것을 알 수 있다.

간선 2,3개를 가진 정점을 제거할 경우

 

 

설계

1. 주어지는 간선의 데이터를 인접리스트 배열에 저장한다.
2. 1번 쿼리가 주어지는 경우, 해당 정점의 간선의 갯수로 그래프의 수를 파악한다.
   1. 해당 정점의 간선의 갯수가 2개 이상인 경우, "yes"를 출력한다.
   2. 아닌  경우, "no"를 출력한다.
3. 2번 쿼리가 주어지는 경우, 무조건 2개의 그래프로 나눠지기 때문에 "yes"를 출력한다.

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		List<Integer>[] list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		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());
			list[a].add(b);
			list[b].add(a);
		}
		
		StringBuilder sb = new StringBuilder();
		int q = Integer.parseInt(br.readLine());
		for(int i=0; i<q; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			if(op==2) {
				sb.append("yes\n");
			}else {
				int idx = Integer.parseInt(st.nextToken());
				if(list[idx].size() >=2) sb.append("yes\n");
				else sb.append("no\n");
			}
		}
		System.out.println(sb.toString());
	}
}