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

1. 문제설명

단절점: 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우

단절선: 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우

주어진 간선 정보를 통해 질의 “t k”의 답을 ‘yes’ 또는 ‘no’로 출력하는 문제이다.

t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

2. 접근 방식

• 트리의 간선 정보를 인접 리스트로 저장한다.
• 질의 t가 1인 경우 (단절점인지)
  • 해당 정점의 간선 개수가 2개 이상인 경우 → “yes” 출력
  • 아닌 경우 → “no” 출력
• 질의 t가 2인 경우 (단절선인지)
  • 무조건 2개의 그래프로 나눠짐 → “yes” 출력

 

3. 틀린 이유 설명

트리 문제여서 BFS로 풀이하려고 헀지만 적절한 방법이 아니었다.

단순히 트리의 구조에 대한 문제이다.

 

4. 올바른 접근 방식 및 해결 방식

REF) 

https://loosie.tistory.com/522

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

 

1. 트리에서 정점이 없어지는 경우 (t ==1)

연결되어 있는 간선의 개수로 파악할 수 있다.

해당 정점이 없어지게 되면 해당 간선의 갯수만큼 그래프가 생기게 된다.

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

 

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

 

 

 

2. 트리에서 간선이 없어질 경우 (t == 2)

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

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

 

5. 최종 코드

import java.io.*;
import java.util.*;

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()); // 트리의 정점 개수
        List<Integer>[] list = new ArrayList[n+1]; // 간선 정보 저장 (인접 리스트)
        for(int i=0; i<n+1; i++) { // 리스트 초기화
            list[i] = new ArrayList<>();
        }
        StringTokenizer st;
        for(int i=1; i<n; 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);
        }

        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());
            if(t == 1) { // 질의 t가 1인 경우 (단절점인지)
                // 해당 정점의 간선 개수가 2개 이상인 경우
                if (list[k].size() >= 2) System.out.println("yes");
                else System.out.println("no"); // 아닌 경우
            } else { // 질의 t가 2인 경우 (단절선인지)
                // 무조건 2개의 그래프로 나눠짐
                System.out.println("yes");
            }
        }
    }
}

 

6. 시간복잡도

정점의 개수가 N이고, 질의의 개수가 Q일 때 $O(N + Q)$