Union & Find (집합의 표현, 여행가자)

[집합의 표현 - 1717]

 

 

* 조건

• 0~n까지의 수에 대한 집합관계가 주어진다
• 0: 합집합
• 1: 같은 집합인지 판단 (True or False)

 

* 알고리즘

• Union & Find

 

* 로직

• 자기자신을 부모로 갖는 parent[] 배열을 선언한다
• 0이 오면(합집합)
  • a와 b가 같은 집합이 아니라면 a의 최상단 부모를 b에 붙여준다 (반대로도 가능)
• 1이 오면
  • a와 b가 같은 집합인지 판별한다

 

import java.util.*;
import java.io.*;

public class Problem_1717 {

    static int N;
    static int M;
    static int[] parent;

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

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for(int i=0; i<M; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int operation = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            //union
            if(operation == 0){
                if(!isSameParent(a, b)){
                    doUnion(a, b);
                }
            }

            //find
            else if(operation == 1){
                if(isSameParent(a, b)){
                    System.out.println("YES");
                }
                else System.out.println("NO");
            }
        }

    }

    private static boolean isSameParent(int a, int b) {
        int a_parent = findParent(a);
        int b_parent = findParent(b);
        
        return a_parent == b_parent;
    }

    private static int findParent(int num) {
        if(parent[num] == num){
            return num;
        }
        return parent[num] = findParent(parent[num]);
    }

    private static void doUnion(int a, int b) {
        int b_parent = findParent(b);
        parent[b_parent] = a;
    }
}

 

 

[여행 가자 - 1976]

 

 

* 조건

• 도시의 수 N이 주어진다 (<= 200)
• 여행 일정에 속한 도시의 수 M이 주어진다(<=1000)
• N*N 인접행렬이 주어진다
• 여행 계획이 가능한지의 여부를 판단한다

 

* 알고리즘

• Union & Find

 

* 로직

• 인접행렬의 정보를 활용해 union find를 진행하면 집합의 관계(parent[])를 만들 수 있게된다
• 만들어진 집합의 관계를 이용해 여행 계획에 있던 도시들을 갈 수 있는지 여부를 판단한다

 

import java.io.*;
import java.util.*;

public class Problem_1976 {

    static int N;
    static int M;
    static int[][] map;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());    //도시의 수
        M = Integer.parseInt(br.readLine());    //여행 계획에 속한 도시들의 수

        map = new int[N+1][N+1];
        parent = new int[N+1];
        for(int i=1; i<=N; ++i){
            parent[i] = i;
        }

        for(int i=1; i<=N; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=1; j<=N; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1){
                    if(!isSameParent(i, j)){
                        union(i, j);
                    }
                }
            }
        }

        String travelPlan = br.readLine();
        st = new StringTokenizer(travelPlan, " ");
        ArrayList<Integer> travelList = new ArrayList<>();
        while (st.hasMoreTokens()){
            travelList.add(Integer.parseInt(st.nextToken()));
        }

        boolean find = true;
        for(int i=0; i<travelList.size()-1; ++i){
            int start = travelList.get(i);
            int depart = travelList.get(i+1);

            if(!isSameParent(start, depart)){
                find = false;
                break;
            }
        }

        if(!find) System.out.println("NO");
        else System.out.println("YES");
    }

    private static void union(int start, int depart) {
        int start_parent = findParent(start);
        int depart_parent = findParent(depart);

        parent[start_parent] = depart_parent;
    }

    private static boolean isSameParent(int start, int depart) {        
        int start_parent = findParent(start);
        int depart_parent = findParent(depart);

        if(start_parent == depart_parent){
            return true;
        }
        return false;
    }

    private static int findParent(int num) {
        if(parent[num] == num){
            return num;
        }
        return parent[num] = findParent(parent[num]);
    }
}

 

굳이 map을 안만들고 포문으로만 해결해도 됐던 문제였다. (값이 1이면 포문의 i,j를 넣어주는 식으로)

본능적으로 작성하지 말고 한번 더 생각하자..!