백준 17352 여러분의 다리가 되어 드리겠습니다!

 

package algostudy09_BOJ_17352;

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

public class Review {
	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int n = Integer.parseInt(br.readLine());
		
		int bridge[] = new int[n+1];
		for(int i = 1;  i <=n ; i++) {
			bridge[i] = i;
		}
		
		for(int i = 0 ; i < n-2 ; i++) {
			String tmp[] = br.readLine().split(" ");
			//주어진 다리들을 연결
			union(bridge,Integer.parseInt(tmp[0]),Integer.parseInt(tmp[1]));
		}

		//set에 넣어서 중복 제거
		HashSet<Integer> set = new HashSet<Integer>();
		for(int i = 1 ; i <=n ; i++) {
			set.add(getParent(bridge, bridge[i]));
		}
		
		for(int num :set) {
			System.out.print(num+" ");
		}
		
	}
	
	public static int getParent(int bridge[],int a) {
		if(a == bridge[a]) {
			return a;
		}else {
			return getParent(bridge,bridge[a]);
		}
	}
	
	public static void union(int bridge[],int a,int b) {
		a = getParent(bridge,a);
		b = getParent(bridge,b);
		
		if(a<b) {
			bridge[b] = a;
		}else {
			bridge[a] = b;
		}
		
	}
	
	
}

풀이법

정수 두개를 받을때 getParent 함수를통해 연결된 부모의 값을 받아오고

union함수를 이용하여 부모의 값으로 연결해준다

그후 set을 통해여 중복을 제거하고 하나씩 풀력해준다.