여행 가자

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

풀이

최근 유니온-파인드 문제를 중점적으로 풀며 알고리즘을 익히고 있어 이번 문제도 유니온-파인드 알고리즘 문제다.

풀이는 간단하다.

도시끼리 경로가 있다면 여행을 할 수 있다는 의미이기 때문에 같은 집합으로 묶어준다.
이 때 1->3과 3->1은 같은 경로고 1번 도시와 3번 도시는 이미 1->3 경로를 탐색할 때 집합으로 묶었기 때문에 3->1 경로같은 경우 탐색하지 않는다.

이런식으로 집합을 만들고 이제 여행 도시를 하나씩 find 메소드를 통해 해당 도시와 연결된 경로의 부모를 찾아 저장하고, 이렇게 찾은 부모들이 모두 같다면 해당 경로로 여행이 가능하고, 하나라도 다르다면 불가능하다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static int[] p;
    static ArrayList<ArrayList<Integer>> party = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        input = br.readLine().split(" ");
        m = Integer.parseInt(input[0]);

        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for(int j = 0;j<line.length;j++) {
                graph[i + 1][j + 1] = Integer.parseInt(line[j]);
            }
        }
        String[] last = br.readLine().split(" ");
        int[] route = new int[last.length];
        for(int i = 0;i<last.length;i++) {
            route[i] = Integer.parseInt(last[i]);
        }

        //printGraph(graph);

        p = new int[n + 1];

        for(int i = 0;i<=n;i++)
            p[i] = -1;

        for(int i = 1;i<=n;i++) {
            for(int j = i;j<=n;j++) {
                if(graph[i][j] == 1) {
                    union(i,j);
                }
            }
        }

        ArrayList<Integer> roots = new ArrayList<>();
        for (int j : route) {
            int root = find(j);
            roots.add(root);
        }

        int temp = roots.get(0);
        for(int a : roots) {
            if(a != temp) {
                System.out.println("NO");
                System.exit(0);
            }
            temp = a;
        }

        bw.write("YES\n");
        bw.close();
        br.close();
    }

    private static void union(int a, int b) {
        int ar = find(a);
        int br = find(b);

        if(ar != br) {
            if(ar == p[ar])
                p[br] = ar;
            else
                p[ar] = br;
        }
    }

    private static int find(int a) {
        if(p[a] < 0 || p[a] == a) {
            return a;
        }
        else {
            int y = find(p[a]);
            p[a] = y;
            return y;
        }
    }
}