[JAVA] 백준 q14675 - 단절점과 단절선

2023. 9. 19. 15:04· 알고리즘/백준
 

14675번: 단절점과 단절선

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정

www.acmicpc.net


> 의식의 흐름

간선은 끊으면 어떤 경우여도 그래프가 2개로 나뉘니까 yes일거고 정점은 다른 정점 한 개랑 연결된 애만 아니면 되겠지..?

 

> 풀이 과정

1. 각 정점에 대해 연결된 정점 번호를 담을 ArrayList 생성

ArrayList<ArrayList<Integer>> links = new ArrayList<>();

for(int i=0;i<=N;i++){
   links.add(new ArrayList<Integer>());
}


2. 입력으로 주어지는 간선 정보를 바탕으로 1번에서 생성한 ArrayList를 채운다.
3-1. 질의 유형이 `1`인 경우, 단절점인지 판단한다.

  • k번 정점과 연결된 정점이 1개이면, k번 정점이 제거되어도 그래프가 2개로 나눠지지 않으므로 "no"를 출력한다.
  • k번 정점과 연결된 정점이 2개 이상이면, k번 정점이 제거되었을 때 그래프가 2개 이상으로 나눠지므로 "yes"를 출력한다.

3-2. 질의 유형이 `2`인 경우, 단절선인지 판단한다.
이때, 간선을 끊으면 항상 그래프가 2개 이상으로 나눠지므로 무조건 "yes"를 출력한다.
4. q개의 질의에 대해 3번 과정을 반복한다.

 

> 코드

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

public class Main {
    public static int N, q;
    public static ArrayList<ArrayList<Integer>> links = new ArrayList<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine()); // 정점의 개수
        for(int i=0;i<=N;i++){
            links.add(new ArrayList<Integer>());
        }

        for(int i=0;i<N-1;i++){ // 간선 정보
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            links.get(a).add(b);
            links.get(b).add(a);
        }

        q = Integer.parseInt(br.readLine()); // 질의의 개수
        for(int i=0;i<q;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken()); // 질의 유형
            int k = Integer.parseInt(st.nextToken()); // k번째 정점/간선

            switch (t){
                case 1: // 단절점인지
                    if(links.get(k).size()==1){
                        // 연결된 정점 개수가 1개인 경우
                        bw.write("no\n");
                    }
                    else{
                        bw.write("yes\n");
                    }
                    break;
                case 2: // 단절선인지
                    // 간선을 끊으면 무조건 2개 이상의 그래프로 나뉨
                    bw.write("yes\n");
                    break;
            }
        }

        bw.flush();

        br.close();
        bw.close();
    }
}
저작자표시 (새창열림)

'알고리즘 > 백준' 카테고리의 다른 글

[JAVA] 백준 q1991 - 트리 순회  (0) 2023.09.21
[JAVA] 백준 q11725 - 트리의 부모 찾기  (0) 2023.09.21
[JAVA] 백준 q7662 - 이중 우선순위 큐  (0) 2023.09.15
[JAVA] 백준 q4358 - 생태학  (0) 2023.09.14
[JAVA] 백준 q2580 - 스도쿠  (0) 2023.08.08
'알고리즘/백준' 카테고리의 다른 글
  • [JAVA] 백준 q1991 - 트리 순회
  • [JAVA] 백준 q11725 - 트리의 부모 찾기
  • [JAVA] 백준 q7662 - 이중 우선순위 큐
  • [JAVA] 백준 q4358 - 생태학
하얀 돌덩이
하얀 돌덩이
하얀 돌덩이
돌덩이
하얀 돌덩이
전체
오늘
어제
  • 분류 전체보기 (59)
    • 개발 일지 (2)
    • 스프링 (1)
    • JAVA (2)
    • 딥러닝 (10)
    • 알고리즘 (43)
      • 개념 (4)
      • 프로그래머스 (5)
      • 백준 (34)
    • 후기 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
하얀 돌덩이
[JAVA] 백준 q14675 - 단절점과 단절선
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.