[백준]JAVA - 1976번: 여행 가자

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

1976번: 여행 가자

🔶 풀이

유니온-파인드 문제.

 

1 → 3 으로 가려고할 때, 바로 연결되어있지 않아도 1 → 2 → 3 이 연결되어있다면 갈 수 있다.

즉, 가고자하는 경로가 쭉 이어져있으면 여행이 가능하다는 뜻이다.

 

유니온-파인드에 대해서 처음 접하신 분들은 아래 링크를 보고 오는 것을 추천한다.

유니온-파인드를 이용한 대표적인 알고리즘을 설명하고있다.

최소 비용 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) 정의

 

<최종코드>

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

public class Main {
    static int parent[];
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        parent = new int[N+1];
        for (int i=1; i<=N; i++) {
            parent[i] = i;
        }
        
        for (int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=1; j<=N; j++) {
                int tmp = Integer.parseInt(st.nextToken());
        		
                if (tmp == 1) {
                    union(i, j);
                }
            }
        }
        
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        for (int i=1; i<M; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            if (find(start) != find(tmp)) {
                System.out.println("NO");
                return;
            }
        }
        
        System.out.println("YES");
    }
    
    public static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
    	
        return parent[x] = find(parent[x]);
    }
    
    public static void union(int a, int b) {
        int A = find(a);
        int B = find(b);
    	
        if (A != B) {
            if (A > B) parent[A] = B;
            else       parent[B] = A;
        }
    }
}