[자바] 백준 24461 - 그래프의 줄기 (java)

목차

문제 : boj24461

 

 

필요 알고리즘

• 그래프 이론, 브루트 포스
  
  • 별다른 알고리즘 지식은 필요하지 않긴한데, 구현이 어려울 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  아래와 같은 그래프를 생각해보자.

 

 

  각 정점에 대해 현재 연결된 간선의 수를 적어보면 아래와 같다. 이번에 제거될 가장자리 정점은 연결된 간선의 수가 '1'인 정점들임을 알 수 있다.

 

 

  한 번 삭제된 후엔 아래와 같이 된다. 그리고 그래프의 줄기가 남게되므로 종료된다. 그래프의 줄기만 남는 경우는 모든 정점들이 연결된 간선이 2 이하일 때 이다.

 

 

  그래프의 줄기는 정점이 1개만 남았어도 가능하다. 즉, 아래와 같은 경우, '3'이 답이다.

 

 

 

  구현에 따라 다르겠지만, 내 경우 아래와 같은 경우와 위의 경우를 나누기 위해 코드에 exceptionChk라는 부분을 두었다. 혹시 왜 틀렸는지 모르겠다면 한번 확인해보자.

 

 

---

  풀기 위해 필요한 내용은 위의 내용들로 충분하고, 이제 적절히(?) 구현해주면 된다. 디테일한 부분은 코드로 있으나, 대강의 내 구현 로직은 아래와 같다.

 

1. 연결된 간선이 3 이상인 정점은 미리 remain에 담아두었고, remainCnt에 갯수를 세두었다.

2. 이후 remainCnt가 0이 될 때 까지 이하의 로직을 진행한다.

2.1 연결된 간선이 1개인 정점을 제거한다.

2.2 제거할 때, 그 정점과 간선으로 연결된 정점에 대해 연결된 간선의 수를 줄여준다.

2.3 '2.2'에서 새로 연결된 간선이 1개가 된 정점들은 다음 회차에 한번에 모두 진행하기 위해 별도로 큐에 넣어둔다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] cnt = new int[n];
        Map<Integer, Set<Integer>> edges = new HashMap<>();
        for (int i = 0; i < n; i++) edges.put(i, new HashSet<>());

        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            cnt[a]++;
            cnt[b]++;
            edges.get(a).add(b);
            edges.get(b).add(a);
        }

        Queue<Integer> q = new ArrayDeque<>();
        Set<Integer> remain = new HashSet<>();
        int remainCnt = 0;
        int exceptionChk = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] == 1) q.add(i);
            else if (cnt[i] == 2) exceptionChk++;
            else if (cnt[i] >= 3) {
                remain.add(i);
                remainCnt++;
            }
        }


        while (remainCnt!=0) {
            if (remainCnt == 1 && exceptionChk == 0) {   // exception case
                System.out.println(remain.iterator().next());
                return;
            }

            Queue<Integer> next = new ArrayDeque<>();

            while (!q.isEmpty()) {
                int cur = q.poll();
                int opposite = edges.get(cur).iterator().next();

                cnt[cur]--;
                if (cnt[cur] == 1) exceptionChk--;
                if (cnt[cur] == 2) exceptionChk++;

                cnt[opposite]--;

                if (cnt[opposite] == 1) {
                    exceptionChk--;
                    next.add(opposite);
                }
                if (cnt[opposite] == 2) exceptionChk++;
                if (cnt[opposite] < 3 && remain.contains(opposite)) {
                    remain.remove(opposite);
                    remainCnt--;
                }

                edges.get(opposite).remove(cur);
            }
            q = next;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++)
            if (cnt[i] > 0) sb.append(i).append(' ');
        System.out.println(sb);
    }
}