관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/유니온파인드, 최소신장트리(크루스칼)

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

막무가내막내 2020. 11. 7. 20:48
728x90

www.acmicpc.net/problem/1976

 

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

 

 

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

youngest-programming.tistory.com/427

 

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

www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은..

youngest-programming.tistory.com

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

 

풀이는 다음과 같습니다.

 

[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;
    }
}

 

 

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

 

감사합니다. !!

728x90
Comments