[BOJ] 1976.여행 가자(Union&Find).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

동혁이가 목적을 달성하기 위해서는

여행 계획에 속한 도시들을 모두 방문할 수 있는지 확인해야 한다.

이 말은 즉, 여행 계획에 속한 도시들이 모두 연결되어있어야 한다.

방문할 도시들의 연결 여부는

Union&Find 를 활용해서 구할 수 있다.

두 도시의 Root가 같다 = 두 도시는 연결되어 있다.

이게 포인트다.

***

여기서 큰 실수를 했던건,

두 도시의 Root를 비교해야하는데,

parents를 비교했던 점이다.

두 도시가 연결(union)되면서 Find() 함수가 호출되고,

자연스럽게 두 도시가 Root 정보를 parents에 저장하게 된다.

하지만, 예외 상황으로

리프 노드의 경우 상위 노드들의 union 과정에서 (Find 에 포함되지 않고)

Root 정보를 최신 상태로 갱신하지 못하는 경우가 있다는 것이다.

그래서 마지막에 두 도시의 Root 확인할 때,

parents에 저장된 값을 비교하는 것이 아니라,

find() 함수 결과를 비교해주어야 한다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ1976 {
 
    static int N, M, parents[], plan[];
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        plan = new int[M];
        parents = new int[N];
        // Set
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
        // 도시 정보
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                // 두 도시를 연결
                if(tmp == 1) union(i, j);
            }
        }
        // 여행 계획
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            plan[i] = Integer.parseInt(st.nextToken()) - 1;
        }
        
        boolean isSuccess = true;
        for (int i = 0; i < M - 1; i++) {
            // 두 도시가 연결되어있지 않다면
            if(find(plan[i]) != find(plan[i + 1])) {
                isSuccess = false;
                break;
            }
        }
        
        if(isSuccess) System.out.println("YES");
        else System.out.println("NO");
    }
 
    private static boolean union(int a, int b) {
        
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot == bRoot) return false;
        parents[bRoot] = aRoot;
        
        return true;
        
    }
 
    private static int find(int a) {
        if(a == parents[a]) return a;
        return parents[a] = find(parents[a]);
    }
    
}