<Algorithm> 183. 여행가자(BJO)

1. 1976번 여행가자(BJO)

   사용 알고리즘 :  Union-find

• 다음에 풀 MST 문제를 위해 오랜만에 Union-find를 다시 공부했다.

• 이에 대한 내용은 https://www.crocus.co.kr/683 에 가장 잘 설명되어있다.(친절하게 그림까지! 감사합니다. )

• 요약하면 서로 연결 되어있지 않은 그래프를 합치는 것 Union, 임의의 정점에 대한 루트를 찾는 것이 Find 이다.

• 이문제를 보고 이거 Find로만 풀 수 있을 것 같은데? 라는 착각을 했었다... 당연히 틀렸지만 처음에 반례가 뭐지 하고 한참 고민했다.

• Find만 할 경우 뒤에 나오는 연결을 처리할 수가 없었다. ex) 1-2-9, 3-4-9 순차적으로 처리하면 3의 루트는 1이 아닌 3이 되버린다..

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

import java.util.Scanner;   public class Main {     static int n,m;     static int[] parent,level;     public static void main(String[] args) {         /***************************          * UnionFind를 이용해서 연결이 있을          * 경우 해당 경로들을 Union 시키고          * 루트노드를 맞춰준다. 그 후 경로에          * 대해 루트가 일치하면 YES를 출력한다.          ***************************/         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         m = sc.nextInt();         parent = new int[n];         level = new int[n];         for(int i = 0; i < n; i++) {             parent[i] = i;             level[i] = 1;         }         for(int i = 0; i < n; i++) {             for(int j = 0; j < n; j++) {                 int temp = sc.nextInt();                 if(temp!= 0) {                         union(i, j);                 }             }         }         int prev = sc.nextInt()-1;         for(int i = 1; i < m; i++ ) {             int next = sc.nextInt()-1;             if(!union(prev, next)) {                 System.out.println("NO");                 return;             }             prev = next;         }         System.out.println("YES");     }     private static int find(int v) {         if(v == parent[v]) return v;         else return parent[v] = find(parent[v]);         //find(parent[v]만 하지 않는 이유는 한번 find가          // 발생했을때 처리 상태를 누적하기 위함이다(root노드는 같다)         // 누적함으로서 다음번에 호출이 필요할경우 O(1)의 복잡도를 가진다.     }     private static boolean union(int i, int j) {         int iroot = find(i);         int jroot = find(j);                  if(iroot == jroot) return true;                  if(level[iroot] < level[jroot]) {             int temp = iroot;             iroot = jroot;             jroot = temp;         }         parent[jroot] = iroot;                  if (level[iroot] == level[jroot]) level[iroot]++;         // 크기가 같은경우 붙였을때 1깊이 늘어난다.         return false;     } }   Colored by Color Scripter

cs