백준 1976 여행 가자 (JAVA)

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

1976번: 여행 가자

 

문제 설명

도시의 노드 연결 여부가 알려주면 주어지는 여행 계획을 수행 할 수 있는지 찾는 알고리즘을 구현하는 문제입니다.

 

문제를 풀기 위한 아이디어

예제 입력을 보면 인접 행렬로 입력값을 주어지는 것을 알 수 있습니다. 그러므로 인접 행렬을 이용해 문제를 푸는 방식으로 생각해봤습니다. 

N은 최대 200 이고 M은 1000이하 인 것을 알 수 있습니다. 시간 제한이 2초 이므로 모든 노드를 돌아봐도 시간 초과는 생기지 않습니다. 

 

분리 집합

이 문제를 해결하기 위해 분리 집합 방법을 사용했습니다. Union-Find로 더 잘 알려져 있습니다. 여행 계획에 주어진 도시를 순서대로 갈 수 있는지만 확인 하면 됩니다. 즉 Union-Find로 같은 집합인지 확인만 하면 됩니다. 같은 집합이라는 뜻은 그 노드로 갈 수 있다는 뜻입니다. 

보통의 Union-Find는 트리의 높이만큼 탐색하므로 O(logN)의 시간이 걸립니다. 이런 보통의 Union-Find에서 한 쪽으만 가는 트리가 생길 수 있습니다. 그때는 O(n)이 시간복잡도 입니다. 따라서 효율성을 위해 Find 과정에서 경로 압축을 많이 사용합니다. 이럴 경우 O(a(N))으로 거의 상수시간에 유사해집니다. 

 

전체 코드

import java.util.*;
import java.io.*;

public class 백준_1976_여행_가자 {
    static int arr[]; // 유니온 파인드를 관리 하기 위한 배열
    static int n,m;
    static int graph[][]; // 인접 행렬 그래프
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(buf.readLine());
        m = Integer.parseInt(st.nextToken());
        graph = new int[n+1][n+1];
        int dist[] = new int[m]; // 여행 경로 배열
        arr = new int[n+1];
        for(int i = 1; i <= n; ++i){
            arr[i] = i;
        }
        for(int i = 1; i <= n; ++i){
            st = new StringTokenizer(buf.readLine());
            for(int j = 1; j <= n; ++j){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(buf.readLine());
        for(int i = 0; i < m; ++i){
            dist[i] = Integer.parseInt(st.nextToken());
        }
        
        // 유니온 파인드를 통해 같은 집합 구현하기
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(graph[i][j] == 1){
                    if(find(i) != find(j)){
                        union(i,j);
                    }
                }
            }
        }
        
        // 여행 계획을 탐색하면서 같은 집합인지 검사
        int check = arr[dist[0]];
        boolean ch = true;
        for(int i = 1; i < m; ++i){
              if(check != arr[dist[i]]) {
                  ch = false;
                  break;
              }
        }
        if(ch) System.out.println("YES");
        else System.out.println("NO");
    }
    
    // 유니온 파인드 함수
    public static int find(int a){
        if(arr[a] == a) return a;
        else return arr[a] = find(arr[a]);
    }
    public static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(b >= a) arr[b] = a;
        else arr[a] = b;
    }
}

https://github.com/SeWooooong/CodingTest_Practice/commit/ba3fa38e0e2487d29f2d62db14c34a5b56096b90

[Gold IV] Title: 여행 가자, Time: 196 ms, Memory: 17836 KB -BaekjoonHub · SeWooooong/CodingTest_Practice@ba3fa38