[백준]14675: 단절점과 단절선 - JAVA

[백준]14675: 단절점과 단절선 

14675번: 단절점과 단절선

풀이

이 문제 트리의 성질을 잘 알고있다면 탐색 알고리즘을 사용하지 않고도 풀 수 있는 문제이다.

 

이 문제를 푸는데 필요한 트리의 성질은 다음과 같다.

1. 트리는 사이클이 없고, 모든 정점이 연결되어 있다. (문제에 나와있다.)
2. N개의 정점이 있을때 N-1개의 간선을 가진다. 

입력 받은 정보는 현재 '트리'인 상태이며, 해당 트리가 두 부분으로 나눠지는지 확인하면 된다.

 

우선, t에 2가 입력되었을 때를 먼저 살펴보쟈. t가 2라는건 간선을 하나 지운다는 의미이다. 

현재 트리인 상태에서 어떠한 간선을 하나 지우면 항상 두개의 트리로 나눠질 수 밖에 없다. 

그러므로 항상 yes를 출력한다.

 

t에 1이 입력된 경우를 생각해보자. 1이라는건 정점을 하나 지운다는 의미이다. 

이때는 두 가지 경우가 발생할 수 있다.

1. 루트, 리프 정점을 삭제한 경우
2. 루트, 리프 정점이 아닌 정점을 삭제한 경우

1번이라면 삭제 후에 두개의 트리로 나눠질 수 없고, 2번이라면 삭제 후 두개의 트리로 나눠질 수 있다.

1번인 경우는, 루트나 리프 정점을 삭제한 경우 해당되며 루트나 리프는 다른 정점과 간선의 수가 다르다.

루트나 리프는 연결 간선이 하나밖에 존재하지 않는다. 그러므로 이러한 속성을 사용하여 문제를 풀어주면 된다.

 

코드

import java.util.*;
 
public class Main {
 
    static ArrayList<Integer>[] list;
    static int n;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        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++) {
            int n1 = scan.nextInt();
            int n2 = scan.nextInt();
            list[n1].add(n2);
            list[n2].add(n1);
        }
 
        int q = scan.nextInt();
        for(int i = 0; i < q; i++) {
            int t = scan.nextInt();
            int k = scan.nextInt();
 
            if(t == 2) System.out.println("yes");
            else {
                int count = 0;
                for(int temp : list[k]) {
                    count++;
                }
                if(count >= 2) System.out.println("yes");
                else System.out.println("no");
            }
        }
    }
}