백준 1976 Java 풀이

[1976-여행 가자]

문제

• N 도시의 수
• M 여행 경로의 수
• 인접행렬 입력
• 여행 경로 입력
• 여행 경로가 유효한가?를 묻는 문제다.
• 즉, 인접 행렬에 노드간 간선으로 이루어져 있는지 정보를 주고 여행 경로(노드 이동 경로)가 가능한지 묻는 문제다.

풀이

• 이 문제는 Union Find로 풀이할 수 있다.
• 간선으로 이어진 도시들(노드들)을 합집합으로 같은 루트 노드를 바라보게하고 여행 경로를 순회하면서 같은 루트를 바라보고 있는지 검사하면 문제가 해결된다.

코드

• 입력값과 초기 선언문 때문에 코드가 길지만 위에 풀이한 순서대로 보면 어렵지 않음.

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


public class Main {

    private static int[] parents;
    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());
        int[] route = new int[m];

        parents = new int[n + 1];
        for (int i = 1 ; i <= n ; i++) {
            parents[i] = i;
        }

        for (int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1 ; j <= n ; j++) {
                if (Integer.parseInt(st.nextToken()) == 1) {
                    union(i, j);
                }
            }
        }

        st = new StringTokenizer(br.readLine());

        for (int i = 0 ; i < m ; i++) {
            route[i] = Integer.parseInt(st.nextToken());
        }

        String result = "YES";

        for (int i = 0 ; i < m - 1 ; i++) {
            int rootA = find(route[i]);
            int rootB = find(route[i + 1]);

            if (rootA != rootB) {
                result = "NO";
                break;
            }
        }

        System.out.println(result);
    }

    private static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parents[rootY] = rootX;
        }
    }

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

        return parents[n] = find(parents[n]);
    }
}