[greedy] 친구인가?(Union & Find)

들어가면서

'친구인가?' 문제의 핵심을 파악하고
문제를 풀면서 풀이 방법을 정리해본다.

문제 해석

친구가 될 수 있는가, 없는가를 구해야 한다.

일단 규칙성을 파악해보았다.

각각의 인원을 노드로 생각하고 서로 연결되어 있는 노드는 친구이다.

반면에, 서로 연결되어 있지 않고 서로 중복되는 값이 존재하지 않는 집합 즉,

서로소 집합인 경우에는 친구가 아니라고 볼 수 있다.

전체 코드

import java.util.Scanner;

public class 친구인가{

	static int[] unf;
    
    public static int Find(int v){
    	if(v == unf[v]) return v;
        // 시간복잡도를 줄여준다.
        else return unf[v] = Find(unf[v]);
    }
    
    public static void Union(int a, int b){
    	int fa = Find(a);
        int fb = Find(b);
        
        if(fa != fb) unf[fa] = fb;
    }

	public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        int m = in.nextInt();
        
        unf = new int[n+1];
     
     	for(int i = 1; i <= n; i++) unf[i] = i;
        for(int i = 1; i <= m; i++){
        	int a = in.nextInt();
            int b = in.nextInt();
            
            Union(a,b);
        }
        
        // a와 b가 친구인가?
        int a = in.nextInt();
        int b = in.nextInt();
        
        int fa = Find(a);
        int fb = Find(b);
        
        if(fa == fb) System.out.println("YES");
        else System.out.println("No");
    }
}	

문제 풀이

문제 풀이 과정 영상을 찍어보았다.

velog에서는 동영상 업로드가 안돼서 tistory에 공유했다.

https://hardkeepgoing.tistory.com/222

알게된 점

서로소 집합 문제를 Union과 Find 방법으로 풀이하는 방법을 배웠다.

개개인을 노드로 설정해서 친구일 때 연결시키고 친구가 아닌 경우 연결되지 않도록 설계해주는 것까지는

구현했는데, solution 로직을 풀지 못했다.