백준 [1976] 여행가자 (JAVA)

문제

풀이

bfs나 dfs를 사용해야 하나 고민하다가 도저히 여행이 불가능한 조건을 어떻게 판단하고 종료를 할지 감이 안 잡혀서 힌트를 얻었음.

유니온 파인드 알고리즘을 사용하는 문제라는 것을 파악

 

대표적인 유니온 파인드 문제

백준 [1717] 집합의 표현 (JAVA)

 

유니온 파인드

여러 노드가 존재할 때 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

 

같은 그래프에 있어야 여행이 가능

 

1. 선이 연결된 경우(여행이 가능한 경우)
2. union()을 통해 루트 노드에 합치는 작업을 수행한다. N개의 도시에 대해서 NxN개의 경로 정보를 탐색하며 union 과정을 수행한다.
3. 모두 수행하고 여행 경로에 대해서 첫 번째 여행 경로와 모두 같은 루트 노드를 가지고 있다면 어떻게든 연결이 된다는 의미(루트 노드와 연결 되어 있다면 루트 노드를 통해 다른 노드들도 방문이 가능하다는 걸 의미한다.)
4. 여행 경로 중 첫 번째 루트 노드와 다른 루트 노드를 가지고 있다면 여행이 불가능하므로 NO를 출력, 아니면 YES를 출력

정답코드

package com.baekjoon.data_structure.p1976;

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

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        parent = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                int val = Integer.parseInt(st.nextToken());

                if (val == 1) {
                    union(i, j);
                }
            }
        }

        boolean canTravel = true;

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        for (int i = 1; i < M; i++) {
            int val = Integer.parseInt(st.nextToken());

            if (find(start) != find(val)) {
                canTravel = false;
                break;
            }
        }

        if (!canTravel) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }

    }

    static int find(int x) {
        if (x == parent[x]) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

    static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
}