BOJ G4 1976 여행 가자 JAVA

1976번: 여행 가자

---

문제 읽기

유니온 파인드를 모른 채로 이 문제를 처음 봤다면 인접 리스트 만들어서 DFS로 그래프 탐색을 했을지도 모른다.. 하지만 지금은 유니온 파인드를 알기 때문에, 훨씬 단순하게 생각할 수 있었다.

 

유니온 파인드의 개념이 궁금하면 다음 글을 참고하고 오면 좋다.

분리 집합, Disjoint Set : Union-Find

 

문제를 읽어보면 도시들 사이에 직접적인 연결이 아니어도, 다른 도시를 경유하여 간접적으로 이동할 수 있다면 그 곳은 갈 수 있는 여행 경로이다. 즉, 문제에서 주어지는 여행 계획이 모두 직/간접적으로 연결되어 있으면 가능한 여행 계획이 되는 것이다.

 

따라서 여기에 유니온 파인드를 적용할 수 있다.

---

문제 풀기

유니온 파인드를 적용하여 문제를 해결해보자.

1. 총 N개의 도시의 부모 노드에 해당하는 parent 배열 생성
2. 연결 정보를 입력 받으며, 연결되어 있는 두 도시를 union(a, b)
3. 마지막 여행 계획을 입력 받으며, 계획에 적혀 있는 모든 도시의 부모 노드 확인
   1. 모두 같다면 → 가능한 여행 계획 → “YES”
   2. 하나라도 다르다면 → 불가능한 여행 계획 → “NO”

이와 같은 흐름으로 코드를 작성하면 문제를 쉽게 해결할 수 있다.

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G4_1976_여행가자 {
    static int N, M;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(in.readLine()); //도시의 수
        int M = Integer.parseInt(in.readLine()); //여행 계획에 속한 도시의 수

        parent = new int[N]; //0~N-1까지의 도시
        for (int i = 0; i < N; i++){
            parent[i] = i; //초기화. 각각 다른 집합.
        }
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int j = 0; j < N; j++){
                int connect = Integer.parseInt(st.nextToken());
                if (connect == 1){
                    //집합을 합쳐준다.
                    union(i, j);
                }
            }
        }

        //여행계획. 모두 같은 집합이어야 함
        boolean isALlSame = true;
        StringTokenizer st = new StringTokenizer(in.readLine());
        int root = find(Integer.parseInt(st.nextToken())-1);
        for (int i = 1; i < M; i++){
            if (root != find(Integer.parseInt(st.nextToken())-1)){
                isALlSame = false;
                break;
            }
        }
        System.out.println((isALlSame)? "YES" : "NO");
    }

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

        return parent[i] = find(parent[i]);
    }

    private static void union(int i, int j) {
        int ip = find(i);
        int jp = find(j);

        if (ip != jp){
            parent[ip] = jp;
        }
    }
}