[알고리즘] 백준 1976 여행 가자 -유니온파인드(Union-Find) 자바

www.acmicpc.net/problem/1976

1976번: 여행 가자

 

 

백준 유니온파인드 단계별 풀기의 두번째 문제입니다.

youngest-programming.tistory.com/427

[알고리즘] 백준 1717 집합의 표현 -유니온파인트(Union-find)- 자바

위에있는 저번 문제와 다르게 배열로 입력값을 준다는 점이 좀 다릅니다.

 

풀이는 다음과 같습니다.

 

[Java]

import java.io.FileOutputStream;
import java.util.Scanner;

class Main {
    private static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //도시의 수
        int M = sc.nextInt(); //여행계획 수
        parent = new int[N+1]; // [해당노드] = 최상위부모값
        for (int i=0; i<N; i++){
            parent[i] = i;
        }
        for (int i = 1; i <= N; i++) { //경로잇기
            for (int j = 1; j <= N; j++) {
                int flag = sc.nextInt(); // 방문 여부
                if (flag == 1) { //방문이라면 연결
                    union(i, j);
                }
            }
        }
        //여행 계획
        int prev = sc.nextInt();
        for (int i = 0; i < M-1; i++) {
            if (!isSameParent(prev,sc.nextInt())){
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[y] = x;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다.

 

감사합니다. !!