[백준, Java] 14675번, 단절점과 단절선, (그래프 탐색)

문제 링크

14675번: 단절점과 단절선

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 그래프에 단절점과 단절선의 대한 질문이 입력값입니다.

2. 그래프는 트리의 형태로 주어집니다.

3. 각 질문에 대해서 맞으면 "yes",  틀리면 "no"을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 입력되는 그래프에 맞게 Q개의 질문에 대해서 대답을 진행합니다.

 

3. 질문에 대한 대답을 결과로 출력합니다.

 

 

질문에 대답하기

 

해당 그래프는 트리의 형태로써 사이클이 존재하지 않고, 모두 연결된 그래프입니다.

 

여기서 중요한 것은 사이클이 존재하지 않는다는 것입니다.

 

즉, 한 개의 간선이 없어지면 항상 2개의 그래프로 나뉘어집니다.

 

 

Why?

 

어떤 점을 Root Node로 잡든 위와 같이 트리의 형태로 나뉘어지기 때문에 어떤 간선을 제거하더라도 항상 2개의 그래프로 나뉘어집니다.

 

또한, 단절점을 아닌 것은 해당 점이 리프 노드일 때만 단절점이 불가능합니다.

 

즉, 연결된 간선이 2개 이상 존재할 때 단절점이 되는 것입니다.

 

 

 

정리해서 표현하면

 

1. 단절점 : 연결된 간선이 2개 이상일 때

 

2. 단절선 : 모든 간선은 단절선입니다.

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5

 

Q : 4

 

1 1

 

1 2

 

2 1

 

2 2

 

2. 입력되는 그래프에 맞게 Q개의 질문에 대해서 대답을 진행합니다.

 

입력되는 그래프에 대해서 연결된 간선 개수 정리하기

 

 

점	1	2	3	4	5
연결된 간선 개수	1	2	2	2	1

 

 

질문의 대답하기

 

(1, 1) = 1번째 점이 단절점인가??

 

▶ 연결된 간선의 개수가 1개이기 때문에 단절점이 아닙니다.

 

(1, 2) = 2번째 점이 단절점인가??

 

▶ 연결된 간선의 개수가 2개이기 때문에 단절점이 맞습니다.

 

(2, 1) = 1번째 간선(1 → 2)이 단절선인가??

 

▶ 트리 형태의 그래프에서는 모든 간선은 단절선입니다..

 

(2, 2) = 2번째 간선(2 → 3)이 단절선인가??

 

▶ 트리 형태의 그래프에서는 모든 간선은 단절선입니다..

 

 

모든 질문에 대한 대답 완료!

 

 

3. 질문에 대한 대답을 결과로 출력합니다.

 

질문에 대한 대답을 기준으로 결과 출력

 

no, yes, yes, yes을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 그래프와 질문에 대한 정보를 띄어쓰기 기준 나누었습니다.
• 그래프에 대해서 각 점이 연결된 간선의 개수를 구합니다.
• 질문에 대해서 연결된 간선의 개수에 따라 대답을 진행합니다.
• 대답에 대한 결과를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] cnt = new int[N+1];
        //그래프 정보를 토대로 연결된 간선 개수 정보 저장
        for(int i=1;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            //연결된 간선 개수 증가
            cnt[a]++;
            cnt[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());
            //단절점인가?
            if(t == 1){
                if(cnt[k] == 1){	//연결된 간선의 개수가 1개일 때
                    bw.write("no");
                }else{		//연결된 간선의 개수가 2개 이상일 때
                    bw.write("yes");
                }
            }else{	//단절선인가?
                bw.write("yes");
            }
            bw.newLine();
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
}