[백준] 단계별로 풀어보기(단계:30, 유니온 파인드,JAVA)4195번, 친구 네트워크

문제 링크

4195번: 친구 네트워크

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

유니온 파인드

 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조

Union : 집합끼리 합치는 연산

Find : 집합의 원소가 어디에 속해있는지 확인하는 연산

Union Find - 나무위키

이 문제에 핵심은

1. 친구는 소문자와 대문자로 이루어진다.

2. 친구 관계에 대해 입력을 받을 때마다 친구 네트워크에 몇 명인지 결과로 출력합니다.

 

예제입력1에서 유니온파인드가 어떻게 진행되는지 보여드리겠습니다.

 

※저는 합집합을 진행할 때 집합의 루트 노드가 더 작은 곳을 루트 노드로 하였습니다.

 

빨간색 : 해당 원소의 루트 노드

 

입력값 : Fred Barney

 

해석 : Fred와 Barney는 친구 관계

Fred	Barney
1	2

Fred와 Barney의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

Fred	Barney
1	1

같은 루트 노드의 가진 친구가 2개

출력 : 2

입력값 : Barney Betty

 

해석 : Barney와 Betty는 친구 관계

Fred	Barney	Betty
1	1	3

Barney와 Betty의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

Fred	Barney	Betty
1	1	1

같은 루트 노드의 가진 친구가 3개

출력 : 3

입력값 : Betty Wilma

해석 : Betty 와 Wilma는 친구 관계

Fred	Barney	Betty	Wilma
1	1	1	4

Betty 와 Wilma의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

Fred	Barney	Betty	Wilma
1	1	1	1

같은 루트 노드의 가진 친구가 4개

출력 : 4

 

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 친구관계에 대한 정보를 저장합니다.
• 입력된 친구 관계에 따라 mapInput함수로 HashMap에 저장한 뒤 union함수로 네트워크를 연결합니다.
• BufferedWriter에 union함수로 얻은 네트워크의 친구 수를 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• find는 재귀탐색을 이용하여 루트 노드의 값을 찾는 함수입니다.
• union은 두 집합의 루트 노드의 값을 얻어서 더 작은 값으로 통합하는 함수입니다.
• mapInput은 HashMap에 친구들의 관계를 저장합니다.

결과 코드

import java.util.*;
import java.io.*;
public class Main {
	static int T,result,index;
	static int[] parent,level;	//루트 노드, 루트 노드를 기준으로 개수 배열
	static HashMap<String, Integer> map;	//친구 정보 저장 HashMap
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
        	//각 테스트 케이스 진행
		for(int i=0;i<T;i++) {
			int F = Integer.parseInt(br.readLine());
			index = 0;
			map = new HashMap<>();
			parent = new int[F*2];
			level = new int[F*2];
            		//루트 노드 관련 초기화
			for(int j=0;j<F*2;j++) {
				parent[j] = j;
				level[j] = 1;
			}
            		//친구 관계 정보 입력 받았을 때
			for(int j=0;j<F;j++) {
				st = new StringTokenizer(br.readLine()," ");
				result = 1;
				String friend1 = st.nextToken();
				String friend2 = st.nextToken();
                		//친구 배열 저장
				mapInput(friend1);	
				mapInput(friend2);	
                		//네트워크에 연결된 친구수 BufferedWriter 저장
				bw.write(union(map.get(friend1),map.get(friend2)) + "\n");
			}
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//루트 노드 구하는 함수
	static int find(int n) {
		if(n==parent[n])
			return n;
		return parent[n] = find(parent[n]);
	}
    	//친구들 네트워크에 연결 및 네트워크 친구 수 구하는 함수
	static int union(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x!=y) {
			parent[y]=x;
			level[x] += level[y];
			level[y] = 1;
		}
		return level[x];
	}
    	//친구 정보 HashMap에 저장하는 함수
	static void mapInput(String friend) {
		if(!map.containsKey(friend)) 
			map.put(friend, index++);
	}
}