[백준]#1976 여행 가자

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때(중복 가능) 가능한지 여부를 판별하는 프로그램을 작성하시오.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N * N 행렬을 통해 임의의 두 도시가 연결되었는지에 관한 정보가 주어진다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

예제 입력 1

3
3
0 1 0
1 0 1
0 1 0
1 2 3

예제 출력 1

YES

풀이

이 문제는 Find-Union 알고리즘을 이용해서 풀 수 있었으나 아직 해당 알고리즘이 익숙하지 않아 문제를 보고 바로 떠올리지 못했던게 아쉽다.

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

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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++) {
            String[] input = br.readLine().split(" ");
            for(int j=1; j<=N; j++) {
                int num = Integer.parseInt(input[j-1]);
                if(num==1)
                    union(i, j);
            }
        }

        String[] res = br.readLine().split(" ");

        for(int i=1; i<M; i++) {
            int x = Integer.parseInt(res[i-1]);
            int y = Integer.parseInt(res[i]);

            if(find(x)!=find(y)) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a<b) parent[b] = a;
        else parent[a] = b;
    }

    public int find(int x) {
        if(parent[x] == x)
            return x;

        return find(parent[x]);
    }
}