[BOJ 1717] 여행 가자(Union-Find, Java, 자세한 설명)

## 접근

---

• 여행 경로가 가능한지 알아보기 위해서는, 두 점 사이에 경로가 존재하는지 확인해야 한다. 점들을 경유해서 두 점 사이의 경로가 만들어질 수도 있으므로, 가능한 모든 경로를 찾아봐야 한다. 

 

• 위의 생각은, 점의 갯수가 작을 때는 시간복잡도가 작지만, 점의 개수가 많아지면 시간복잡도로 시간초과가 발생할 수 있다.

 

• 따라서, 점들을 경유해서 두 점 사이의 경로가 만들어지면, 두 점의 경로 유무를 저장해줄 수 있는 자료구조가 필요하다.

 

• 그렇다면, 두 점 사이의 경로가 있는지 확인하는 방법을 정해야 한다. 만약에, N이 200일 때, 모든 점 사이의 경로를 본다면, 최대 200 ^ 200의 시간 복잡도가 발생한다. 무조건 시간초과이다. 연결이 되는 점들을 모두 같은 집합에 넣는 Union-Find 방식을 이용하면, 200 * 200안에 모든 집합을 만들 수 있다. 

 

• 두 점의 루트 노드가 같으면, 연결되어 있다고 판단할 수 있다. Find 연산시에 경로압축최적화를 통해, 시간복잡도를 더 줄여나갈 수 있다.
  * 경로압축최적화 : Find 함수 작성 시에, return을 Find 함수 값을, 검사하고 있는 노드에 넣어주는 것.

 

## 해설코드

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main{
    static int[] root; 
    static int find(int x){
        if(x == root[x])
            return x;
        else
            return (root[x] = find(root[x]));
    }
    
    static void union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        root[rootX] = rootY;
    }
 
     public static void main (String []args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    
    
        int N = Integer.valueOf(br.readLine());
        int M = Integer.valueOf(br.readLine());
        
        root = new int[N + 1];
        for(int i = 0; i <= N; i++)
            root[i] = i;
        
        for(int i = 1; i <= N; i++){
            String[] sArr = br.readLine().split(" ");
            for(int j = 1; j <= sArr.length; j++){
                if(sArr[j - 1].equals("1")){
                    union(i, j);
                }
            }
        }
        
        String[] sArr = br.readLine().split(" ");
        int tmp = find(Integer.valueOf(sArr[0]));
        String answer = "YES";
        
        for(int i = 1; i < sArr.length; i++){
            if(tmp != find(Integer.valueOf(sArr[i]))){
                answer = "NO";
                break;
            }
        }
        
        bw.write(answer + "\n");
        bw.flush();
     }
}