[백준 1976] 여행 가자 (Java)

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

1976번: 여행 가자

풀이

union-find 알고리즘을 이용해 푸는 문제였다.

 

int[][] map : 입력받은 도시 간 연결을 나타내는 행렬을 담음

int[] route : 여행자의 이동 경로 도시 번호를 담음

int[] join : 도시 간 집합 index를 담음. 집합 원소 중 가장 도시 번호가 작은 번호 기준으로 담김.

 

map을 탐색해 1인 경우의 좌표값 i, j를 기준으로 union()메소드에서 집합을 합친다. 이 때 작은 번호 기준으로 집합을 구성하기 때문에 i와 j 중 값이 큰 것을 첫번째 파라미터로 넣는다. 집합을 배정하는 과정이 끝나면 route에 있는 도시 번호들의 집합 번호가 모두 일치한지(같은 집합에 속하는지)를 찾고 하나라도 다른게 있다면 "NO"를 출력하고 그렇지 않으면 "YES"를 출력한다.

 

코드

import java.util.Scanner;

public class Main {

    private static int[] join;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int[][] map = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N ; j++) {
                map[i][j] = scanner.nextInt();
            }
        }

        int[] route = new int[M + 1];
        for (int i = 1; i <= M; i++) {
            route[i] = scanner.nextInt();
        }

        join = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            join[i] = i;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (map[i][j] == 1) {
                    if (i < j) {
                        union(j, i);
                    } else {
                        union(i, j);
                    }
                }
            }
        }

        int index = find(route[1]);
        for (int i = 2; i < route.length; i++) {
            if (index != find(route[i])) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }

    private static int find(int city) {
        if (join[city] == city) {
            return city;
        }

        int p = find(join[city]);
        join[city] = p;

        return p;
    }

    private static void union(int city1, int city2) {
        int x = find(city1);
        int y = find(city2);

        if (x != y) {
            join[x] = y;
        }
    }
}