BOJ 1976

2020-09-26

위 문제는 백준 사이트의 알고리즘 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를 출력한다.

소스코드


import java.util.Scanner;

public class Main {

    private static int[] parent;

    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[] plan = new int[M + 1];
        for (int i = 1; i <= M; i++) {
            plan[i] = scanner.nextInt();
        }

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

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

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

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

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

        int p = find(parent[n]);
        parent[n] = p;

        return p;
    }

    private static void union(int a, int b) {
        int x = find(a);
        int y = find(b);

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

이번 문제는 Union-Find을 사용했습니다.

Disjoint Set이란

서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다.

즉, 공통 원소가 없는, 즉 “상호 배타적” 인 서로소 집합 자료구조입니다.

이것을 표현하기 위해서 사용되는 것이 Union-Find입니다.

Union-Find는 크게 3가지로 구성됩니다.

1. make-set(n)

parent배열의 인덱스번째 방에 인덱스 값을 넣어 유일한 원소로 구성된 새로운 집합을 만듭니다.

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

2.find(x)

x가 속한 집합의 대표값(루트 노드 값)을 반환합니다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

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

        int p = find(parent[n]);
        parent[n] = p;

        return p;
    }

3.union(x, y)

x가 속한 집합과 y가 속한 집합을 합치는 연산으로 이 과정에서 Find가 활용됩니다.

    private static void union(int a, int b) {
        int x = find(a);
        int y = find(b);

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

문제 풀이부분

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

받았던 map의 값 중 1인곳이 있다면 그곳은 연결된부분이기에 union합니다.

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

여행계획의 첫머리 부분을 구해서 index에 넣고, for문을 2번부터 끝까지 다 돌려 봅시다.

만약 나머지 여행계획들의 find를 했을 때 다르다면?

연결이 끊어진 상태이므로 여행이 불가능합니다.

따라서 그때는 No를 출력하고 가능하다면 Yes를 출력합니다.

여행 가자