백준 1976번
https://www.acmicpc.net/problem/1976

문제

---

생각하기

---

• Union-Find 문제이다.

• 여행 방문지들이 모두 같은 최상위 노드를 가지는지 확인하면 된다.

동작

        for (int i = 1; i <= N; i++) {
            for (int node : adjList.get(i)) {
                union(i, node);
            }
        }

adjList 을 순회하면서 연결되어 있는 값들을 그룹으로 묶어주는 union()을 실행한다.

        int parent = find(travels[0]);
        for (int i = 1; i < M; i++) {
            if (parent != find(travels[i])) {
                sb.append("NO");
                return sb.toString();
            }
        }

이후 첫번째 여행지의 최상위 부모와 다른 travel[] 배열의 최상위 부모들이 같은지 확인해서 같은 그룹인지 파악한다.

여기서 내가 처음에 실수한게 find()를 union()을 실행하면서 parents[]에 이미 각 노드들의 최상위 부모가 저장되어 있을 거라고 생각했는데 이게 실수였다.

예시로

union(1, 2) 을 수행: 이제 노드 1과 2는 같은 집합에 속합니다.
parents[1] = 1, parents[2] = 1
union(2, 3)을 수행: 이제 노드 1, 2, 3은 같은 집합에 속합니다.
하지만, parents[2] = 1 이지만, 2와 3이 union이 되었으므로 parents[3] = 2가 된다.

즉, parents[]는 parents[1] = 1, parents[2] = 1, parents[3] = 2
여기서 주목할 점은 노드 3의 최상위 부모가 1임에도 불구하고, parents[3]는 2를 가리킨다는 것이다.
이는 union() 만으로는 모든 노드의 parents 값을 최상위 부모로 직접 갱신하지 않는다는 것을 보여준다.

결국에 이런 예시 때문에 union()연산에서 find()를 해도 부모를 찾을 때는 다시 find()를 수행해서 parents[]배열을 갱신해서 부모를 찾아야 한다.

결과

코드

---

Union-Find

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] parents, ranks, travels;
    private static List<List<Integer>> adjList;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        for (int i = 1; i <= N; i++) {
            for (int node : adjList.get(i)) {
                union(i, node);
            }
        }

        int p = find(travels[0]);
        for (int i = 1; i < M; i++) {
            if (p != find(travels[i])) {
                return "NO";
            }
        }

        return "YES";
    } // End of solve()

    private static void union(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);

        if (aParent != bParent) {
            if (ranks[aParent] < ranks[bParent]) {
                parents[aParent] = bParent;
            } else {
                parents[bParent] = aParent;
                if (ranks[aParent] == ranks[bParent]) {
                    ranks[aParent]++;
                }
            }
        }
    } // End of union()

    private static int find(int node) {
        if (node == parents[node]) return node;

        return parents[node] = find(parents[node]);
    } // End of find()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        adjList = new ArrayList<>();
        travels = new int[M];
        parents = new int[N + 1];
        ranks = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
            parents[i] = i;
        }

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int a = Integer.parseInt(st.nextToken());

                if (a == 1) {
                    adjList.get(i).add(j);
                }
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            travels[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class

플로이드 워셜

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE / 40;
    private static int N, M;
    private static int[] travels;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        floyd();

        int start = travels[0];
        for (int i = 1; i < M; i++) {
            int next = travels[i];

            if (arr[start][next] == INF) {
                sb.append("NO");
                return sb.toString();
            }
            start = next;
        }

        sb.append("YES");
        return sb.toString();
    } // End of solve()

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
                }
            }
        }
    } // End of floyd()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        arr = new int[N + 1][N + 1];
        travels = new int[M + 1];

        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {

                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 0 && i != j) {
                    arr[i][j] = INF;
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            travels[i] = Integer.parseInt(st.nextToken());
        }

    } // End of input()
} // End of Main class