[백준 24461] 그래프의 줄기 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/24461

24461번: 그래프의 줄기

 

문제

그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 0$0$이 아닌 경로이다.

사이클이 존재하지 않는 그래프가 주어진다.

우리는 이 그래프의 정점 중에서 연결된 간선이 하나인 정점을 가장자리 정점이라고 정의하자.

이 그래프의 가장자리 정점을 동시에 없애는 행동을 반복하면서, 그래프가 일직선의 모양이 되면 남아있는 정점의 집합을 그래프의 줄기라고 정의하자. 단, 가장자리 정점의 개수가 둘 이하라면 그래프가 일직선 모양이라고 한다.

 

입력

입력의 첫 번째 줄에는 처음 그래프의 정점의 수 N이 주어진다. (2 ≤ N ≤ 100000)

이후 N-1 줄에 걸쳐 각 간선으로 연결된 두 정점의 번호 a, b가 입력된다. (0 ≤ a, b < N, a≠b)

 

출력

출력의 첫 번째 줄에 그래프의 줄기를 이루는 정점의 번호들을 오름차순으로 정렬하고 공백으로 구분하여 출력한다.

풀이

접근법

1. 한 턴씩 진행하면서 가장자리 정점을 삭제하니까 queue를 사용하면 되겠다.
2. 현재 연결되어 있는 노드를 저장하는 배열, 노드들 중에 가장 많은 노드와 연결되어 있는 애가 몇개랑 연결되어 있는지에 대한 배열이 필요하겠다.
3. 제거해주면서 queue에 있다는 것은 하나만 삭제하면 된다는 뜻이니까, 그걸 삭제해주면서 저 위에 두 배열을 관리해주면 되겠다.
4. 만약 입력이 일자이면 그냥 0 ~ N-1 까지 프린트 !
5. 그렇지 않는다면 다 삭제해주고 0 ~ N-1까지 돌면서 아직 삭제 안된 노드를 출력 !

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 List[N];
        for(int i=0;i<N;i++) list[i] = new ArrayList<>();
        StringTokenizer st;
        for(int i=0;i<N-1;i++) {
            st = new StringTokenizer(br.readLine());
            int u=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
        // 1. 한 턴씩 진행하면서 가장자리 정점을 삭제하니까 queue를 사용하면 되겠다.
        Queue<Integer> queue = new LinkedList<>();
        
        // 2. 현재 연결되어 있는 노드를 저장하는 배열, 
        // 노드들 중에 가장 많은 노드와 연결되어 있는 애가 몇개랑 연결되어 있는지에 대한 배열이 필요하겠다.
        int[] linked = new int[N];
        int[] nodes = new int[N];
        int maxIdx = 0;
        boolean[] removed = new boolean[N];

        for(int i=0;i<N;i++) {
            int n = list[i].size(); // 현재 i와 연결된 노드 개수
            linked[i] = n; // 현재 i와 연결된 노드 개수
            nodes[n]++; // n개 연결된 노드의 개수
            maxIdx = Math.max(maxIdx, n); // 연결된 노드의 최대 개수
        }

        StringBuilder sb = new StringBuilder();
        // 4. 만약 입력이 일자이면 그냥 0 ~ N-1 까지 프린트 !
        if (maxIdx <= 2) { // 만약 최대 2개 연결 == 한줄로 이어짐
            for(int i=0;i<N;i++) sb.append(i).append(" ");
            System.out.println(sb);
            return;
        }

        for(int i=0;i<N;i++) {
            if (list[i].size() == 1) { // 만약 첫번째로 연결된거라면..
                queue.add(i); // 일단 큐에 저장
            }
        }

        while(!queue.isEmpty() && maxIdx > 2) {
            int sz = queue.size();
            // 하나의 턴으로 이루어짐
            for(int i=0;i<sz;i++) {
                int now = queue.poll(); // 이제 삭제할 노드
                removed[now] = true;
                for(int nxt : list[now]) {
                    if (removed[nxt]) continue;
                    
                    // 3. 제거해주면서 queue에 있다는 것은 하나만 삭제하면 된다는 뜻이니까, 
                    // 그걸 삭제해주면서 저 위에 두 배열을 관리해주면 되겠다.
                    nodes[linked[nxt]]--;
                    linked[nxt]--;// 연결된거 --;
                    nodes[linked[nxt]]++;

                    if (nodes[maxIdx] == 0) {
                        while(maxIdx > 0 && nodes[maxIdx] == 0) maxIdx--;
                    }
                    // 만약 삭제했다가 걔가 1개 남은애면 가장자리라는 뜻이니까 그 때 큐에 넣어주기
                    if (linked[nxt] == 1)
                        queue.add(nxt);
                }
            }
        }

	// 5. 그렇지 않는다면 다 삭제해주고 0 ~ N-1까지 돌면서 아직 삭제 안된 노드를 출력 !
        for(int i=0;i<N;i++) {
            if (!removed[i])
                sb.append(i).append(" ");
        }
        System.out.println(sb);

    }
}