[Algorithm] 친구인가? (Disjoint-Set : Union&Find)

설명

반 학생은 N명이다. 각 학생들의 친구관계를 알고 싶다.

모든 학생은 1부터 N까지 번호가 부여되어 있고, 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.

만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면

1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.

그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.

학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.

두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

 

입력

첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이 주어지고,

다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.

마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

 

출력

첫 번째 줄에 “YES"또는 "NO"를 출력한다.

 

예시 입력 / 출력

9 7 1 2 2 3 3 4 1 5 6 7 7 8 8 9 3 8

NO

 

 

 

풀이 과정

Disjoint set은 공통 원소가 없는 서로소 집합 자료구조이다.

학생들을 서로로 집합으로 나누어 a학생과 b학생이 같은 그룹에 속해 있는지 판단한다.

 

Union & Find 알고리즘을 통하여 학생들의 소속그룹을 저장하기 위한 unf배열을 만든다.

그리고 완성된 unf배열을 사용하여 a학생과 b학생이 같은 집합에 들어있는지 확인 후 정답을 출력할 것이다.

 

Union & Find함수의 작업물을 담을 학생 배열(인덱스를 학생번호로 사용하기 위해 n+1)을 하나 만들어준다.

* 초기값은 각각의 인덱스번호 자체를 인덱스의 값으로 넣어준다. 

즉 1번은 1번 그룹에 속해있고, 2번은 2번 그룹에 속해있고, n번은 n번  그룹에 속해있다는 뜻이된다.

index	1	2	3	4	5	6	7	8	9
value	1	2	3	4	5	6	7	8	9

unf = new int[n+1];
for (int i = 0; i <= n; i++) {
  unf[i] = i;
}

 

M개의 학생관계를 입력 받으면서 Union함수의 학생a, 학생b를 매개변수로 호출한다.

for (int i = 0; i < m; i++) {
  int a = sc.nextInt();
  int b = sc.nextInt();
  Union(a, b);
}

 

Union함수안에 매개변수로 들어온 학생a , 학생b을 Find함수의 매개변수로 호출하여 return받은 값을

기준으로 같은 그룹에 속해 있는지 확인한 후 같은 그룹이 아니면 unf[fa] = unf[fb]를 통하여 같은 그룹으로

만들어 준다.

static void Union(int a, int b){ // 전달받은 값이 같은 집합이 되게 만들어 주기 위한 함수
  int fa = Find(a); // * Union함수에 들어온 매개변수는 바로 Find로 찾는다.
  int fb = Find(b); // * Union함수에 들어온 매개변수는 바로 Find로 찾는다.
  if(fa != fb) unf[fa] = unf[fb]; // return받은 값이 같지 않으면 같은 집합이 되게 만들어 주는 작업.
}

 

Find함수안에 매개변수로 들어온 학생의 값(v)을 unf배열에서 확인한다.

조건이 ture면 현재 학생의 소속그룹이 자기 자신이다. 자기 그룹을 return한다.

false일 경우 해당 해당 학생은 어딘가의 그룹에 속해있다는 뜻이 된다.

즉 이 경우 재귀함수를 호출하여 재귀 끝의 return값(소속그룹)을 기준으로

재귀를 타고 왔던 중간 중간의 모든 학생(v)를 같은 집합값을 갖도록 만들어준다.

-> 이부분이 아래 로직의 return unf[v] = Find(unf[v]); 이다. (여기서 unf[v] 하나로 시간복잡도를 대폭 줄여준다)

static int Find(int v){
  if(v == unf[v]){
    return unf[v];
  }else {
    // 재귀함수로 재귀끝에 return값을 기준으로 같은 집합이 되게 만들어주는 작업
    return unf[v] = Find(unf[v]); // unf[v]을 통하여 지나간 학생의 값을 다 같은 그룹으로 바꿔준다.
  }
}

 

unf배열에 학생들과 그들이 속상 그룹이 완성되면 마지막 학생을 비교해준다.

sc.nextInt();
int b = sc.nextInt();
int fa = Find(a); // a학생
int fb = Find(b); // b학생
if(fa==fb) { // 같은 그룹인가?
  System.out.println("YES");
}else {
  System.out.println("NO");
}

 

 

 

 

풀이

public class Main {
    static int n; // 학생 수
    static int m; // 숫자쌍의 개수
    static int[] unf; // Union&Find배열

    static int Find(int v){
        if(v == unf[v]){ //
            return unf[v];
        }else {
            return unf[v] = Find(unf[v]);
        }
    }
    static void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        if(fa != fb) unf[fa] = unf[fb];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        unf = new int[n+1];
        for (int i = 0; i <= n; i++) {
            unf[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            Union(a, b);
        }
        // 정답 확인.
        int a = sc.nextInt();
        int b = sc.nextInt();
        int fa = Find(a);
        int fb = Find(b);
        if(fa==fb) {
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    }
}

 

---

 

 

정리 :

알고리즘를 전반적으로 이해하고 기본적인 알고리즘의 패턴은 외우는게 더 효율적일것 같다..