[BOJ] [JAVA] 31423번 신촌 통폐합 계획

31423번: 신촌 통폐합 계획

Union Find에서 Path Compression과 방식이 유사한 것 같아 작성한다. (아닐수도,,,)

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

public class Main {
   
    static String[] str;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        str = new String[n + 1];
        
        for (int i = 1; i <= n; i++) str[i] = br.readLine();
        
        // 자신의 바로 오른쪽 노드 정보
        int [] right = new int[n + 1];
        
        // 같은 집합에 속해있는 원소 중 가장 오른쪽에 있는 노드 정보
        int [] child = new int[n + 1];
        
        for (int i = 0; i < n - 2; i++) {
           st = new StringTokenizer(br.readLine());
           int a = Integer.parseInt(st.nextToken());
           int b = Integer.parseInt(st.nextToken());
           
           // a가 가장 오른쪽이었다면
           if (right[a] == 0) {
              right[a] = b;
           } 
           // a의 바로 오른쪽에 노드가 이미 존재한다면
           // a의 가장 오른쪽을 바꿔준다.
           else {
              right[child[a]] = b;
           }
           // 자식(가장 오른쪽) 정보 갱신
           if (child[b] == 0) {
              child[a] = b;
           } else child[a] = child[b];

        }
        
        st = new StringTokenizer(br.readLine());
       int a = Integer.parseInt(st.nextToken());
       int b = Integer.parseInt(st.nextToken());
       
       if (right[a] == 0) {
          right[a] = b;
       } else {
          right[child[a]] = b;
       }
       if (child[b] == 0) {
          child[a] = b;
       } else child[a] = child[b];
       
       while (right[a] != 0) {
          sb.append(str[a]);
          a = right[a];
       }
       sb.append(str[a]);
       System.out.println(sb);
    }
}