[백준] 1976번 여행 가자 풀어보기 [Java]

 

알고리즘 문제를 푸는 언어를 자바로 바꾸고, 유니온 파인드 문제를 처음 풀어본다. 그래서 처음에는 bfs로 푸는 건가 하다가, 유니온 파인드 가 생각나서 풀 수 있었다.

 

👨‍🏫 풀이

다음 도시로 여행을 하려면, 다음 도시와 어떤 경로든 이어져 있어야 한다. 서로가 이어져 있는지 여부를 체크할 때는 유니온 파인드를 쓰면 된다.

find로 서로가 같은 parent를 공유하고 있는지 여부를 찾고, 만약 같은 parent를 공유하고 있다면, 갈 수 있는 경로가 있다는 것으로 간주할 수 있다.

각 도시를 연결할 때는 값이 작은 것을 parent로 만든다라는 것을 따르면 된다! (큰 것으로 기준을 두어도 됨 일관성있게만 기준을 만들기)

만약 두 노드의 부모가 다르면, 갈 수 없는 루트인 것이다.

 

👨🏻‍💻 코드

package 번1976;

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

public class Main {
    static int N,M;
    static boolean[][] map;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N][N];
        parent = new int[N];
        for(int i = 0 ; i < N ; i++) {
            parent[i] = i;
        }
        for(int i = 0 ; i < N ; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < N ; j++){
                if(st.nextToken().equals("1")){
                    union(i,j);
                }

            }
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()) - 1;
        boolean isPossible = true;
        for(int i = 0 ; i < M - 1 ; i++) {
            int cur = Integer.parseInt(st.nextToken()) - 1;
            if(find(start) != find(cur)) {
                isPossible = false;
            }

            start = cur;
        }

        if(isPossible)
            System.out.println("YES");
        else
            System.out.println("NO");

    }

    private static void union(int i, int j) {
        i = find(i);
        j = find(j);
        if(i != j) {
            if(i < j) parent[j] = i;
            else parent[i] = j;
        }
    }

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