문제 구성 📖

코딩테스트 사이트 : 백준
난이도 : 골드4
풀이 날짜 : 2022.06.25
사용한 풀이 방법 : UnionFind

문제링크

https://www.acmicpc.net/problem/1717

목차

• 유니온 파인드란?
  • 유니온 파인드 알고리즘 이론
  • 유니온 파인드 예제 코드
  • 유니온 파인드 테스트
• 백준 문제
  • 풀이법
  • 제출 코드
    
    
    
    
    
    

유니온 파인드란?

• 그래프 알고리즘으로 두 노드(=지점,도시등)가 같은 그래프에 속하는 지 판별하는 알고리즘이다.
  • 판별이 핵심
• 서로소 집합, 상호 배타적 집합으로도 불린다.
• 트리 구조로 이루어진 자료구조이다.

알고리즘 이론

예를 들어 각각 독립적으로 자유분방하게 여러 노드가 존재한다고 가정하자
아래 그림은 6개의 노드가 존재하고, 모두 자기 자신을 가리킨다고 할 수가 있다.

예시 상황

• 여섯개의 노드가 가리키는 부모노드는 자기 자신임으로 배열을 사용하여 아래와 같이 표현할 수 있다.

첫번째 노드 연결

1번 노드와 2번 노드가 연결되었다고 해본다.

• 이때 컴퓨터상에서 1과 2가 연결되었다는 것을 표현하기 위해, 1번 노드와 2번 노드 중에 작은 수를 배열의 값으로 넣어준다.

• 이렇게 부모를 합칠때 일반적으로 더 작은값쪽으로 합치는데, 이것을 Union이라고 한다.

두번째 노드 연결

이번에는 2번과 3번 노드가 연결 되었다고 해보자.

• 당연히 이번에도, 2번 노드와 3번 노드중에 작은 수로 값을 넣어준다.

여기서 유니온 파인드의 핵심,
1번 노드와 3번 노드는 같은 그래프에 있는데, 어떻게 연결되었다고 파악할 수 있을까요?

• 각 부모 노드만 보고는 한번에 파악할 수 없으니, 재귀함수로 확인을 한다.
• 3번 노드의 부모인 2번노드를 찾고, 또 다시 2번노드의 부모인 1번 노드를 찾아 올라가는 형태인 거죠.
• 찾은 부모의 노드가 자기 자신을 가리켰을 때, 더이상 부모노드가 없음을 확인하고 그 값을 넣는 것이죠,

• 위와 같이 세가지 노드의 가리키는(부모노드)의 값이 1이기 때문에, 모두 같은 그래프에 속한다고 할 수 있다.
• 이것이 바로, Union으로 찾았다고 해서, Union-Find라고 한다.

코드로 보면 이해가 될 것이다.

예제 코드

• 먼저 부모노드를 재귀함수로 구현을 해야한다.
• 탈출 조건은 부모노드가 자기자신이면 뿌리라는 것이니 탈출한다.

getParent 메소드

// 부모 노드 얻기
public static int getParent(int[] parent, int x){
    if(parent[x] == x) return x; // 자기자신을 가리킨다면 반환 
    return parent[x] = getParent(parent, parent[x]);
}

• 그 다음이제 두 노드를 연결한다고 할 때, 두 노드가 가리키는 부모노드를 통일 시켜야한다.
• 여기서 작은 수로 합쳐주면 된다.

unionParent 메소드

// 두 부모 노드 합치기
public static void unionParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);
        if(x > y)  parent[x] = y;
        else parent[y] =x ;
    }

• 마지막, 유니온파인드의 핵심
• 두 노드가 같은 그래프에 존재하는지 알려주는 메소드를 만들면 된다.
• 비교하는 방법은, 두 부모노드가 같은지 유무만 파악하면 된다.

findParent

public static boolean findParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);
        return x == y;
        
        //풀어 쓰면, 
        //if(x==y) return true;
        //else return false;
    }

테스트

이제 작성한 코드를 테스트 해보자
아래와 같이 문제가 주어졌을 때, 풀어 보자

• 1번 노드 부터 2,3,4 노드가 연결되어 있고
• 5번과 6번노드가 따로 연결되어 있는 상황이다.

import java.util.Arrays;
public class unionFindTest {
    // 부모노드 얻기
    public static int getParent(int[] parent, int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent, parent[x]);
    }
    // 두 부모 노드 합치기
    public static void unionParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);
        if(x > y)  parent[x] = y;
        else parent[y] =x ;
    }
    // 부모가 같은지 확인 -> 즉, 같이 연결되어 있는지 확인
    public static boolean findParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);
        return x == y;
    }
    
    
    // 테스트 코드 
    public static void main(String[] args) {
        
        int[] parent = new int[7];
        for(int i =1 ; i< parent.length; i++){
            parent[i] = i; // 모든 부모노드 초기화
        }
        unionParent(parent, 1,2);
        unionParent(parent, 2,3);
        unionParent(parent, 3,4);
        unionParent(parent, 5,6);

        findParent(parent, 1,4); // true
        findParent(parent, 4,5); // false
    }

}

• 각 부분마다 System.out.println(Arrays.toString(parent)); 넣어주면 아래와 같다.
  

• 그래서 결론적으로 parent 배열은 아래와 같이 만들어 진다.

백준 문제

집합의 표현 풀이법

문제 조건

• n+1개의 집합을 이루고 있다
• 여기서 0이면 합집합 연산을, 1이면 같은 집합안에 있는지 유무를 리턴한다.
• 즉, 출력은 1일때만 하면 된다.

예제 해석

• 위 예제를 그림으로 도식화하면 아래와 같다.

• 이 다음 입력값이 1 1 7로 같은 집합안에 있는지 유무를 파악해야한다.
• 1 과 7은 연결되어 있지 않음을 알 수 있다
  • NO를 출력한다.

• 이 다음 입력값이 1 7 1로 같은 집합안에 있는지 유무를 파악해야한다.
• 1 과 7은 연결되어 있지 않음을 알 수 있다
  • NO를 출력한다.

• 다음 마지막 입력값이 1 1 1로 같은 집합안에 있는지 유무를 파악해야한다.
• 1 과 1은 연결되어 있음을 알 수 있다
  • YES를 출력한다.

제출 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] parent = new int[N+1];

        for(int i =0 ; i< parent.length; i++){
            parent[i] = i;
        }

        int order;
        int x;
        int y;
        StringBuilder sb =new StringBuilder();
        
        // 한줄 한줄 M번 읽기
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            order = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            if(order == 0){
                unionParent(parent, x,y);
            }

            if(order == 1){
                if(findParent(parent,x,y)) sb.append("YES");
                else sb.append("NO");
                sb.append("\n");
            }
        }
        System.out.println(sb.toString());
        br.close();


    }
    
    // 부모노드 얻기
    public static int getParent(int[] parent, int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent, parent[x]);
    }

    // 두 부모 노드 합치기
    public static void unionParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);

        if(x > y)  parent[x] = y;
        else parent[y] =x ;
    }
    // 부모가 같은지 확인 -> 즉 같이 연결되어 있는지 확인
    public static boolean findParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);

        return x == y;
    }
}

• 통과