[Algorithm] 백준 유니온 파인드문제 - 여행 가자(1976) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드문제 여행 가자 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n; // n 개의 도시
    static int m; // 들려야 하는 m개 도시
    static int[] parent; // union find
    static List<Integer> nodes = new ArrayList<>(); // 도시 번호 저장
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = parseInt(br.readLine());
        m = parseInt(br.readLine());
        
        parent = new int[n + 1]; // 초기화
        for (int i = 0; i <= n; i++) parent[i] = i; // 루트 노드 설정하기
        
        for (int row = 1; row <= n; row++) {
            // 유니온 파인드를 위해 중복되는 경로를 제거하기 위해 대각선 기준 오른쪽 탐색
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int col = 1; col <= n; col++) {
                int link = parseInt(st.nextToken());
            
                if (col > row) { // 링크가 연결되어 있다면 row의 도시 번호를 기준으로 합치기
                    if (link == 1) union(find(row), find(col));
                }
            }      
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) nodes.add(parseInt(st.nextToken()));
       
        boolean result = isSameRoot(); // 도시가 같은 루트를 공유하는지 판단
        System.out.println(result ? "YES" : "NO");
    }
    
    static boolean isSameRoot() {
        
        if (m == 0) return true; // 만약 들려야 하는 도시가 0이라면 종료
        boolean check = true; // 루트가 같은지 판단
        
        int root = find(nodes.get(0));
        for (Integer node : nodes) {
            if (!(root == find(node))) { // 루트가 다르다면 간선이 존재하지 않음
                check = false;
                break;
            }
        }
        
        return check;
    }
   
    
    static int find(int x) { // find 경로 압축
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    
    static void union(int v1, int v2) {
        parent[v1] = v2;
    } // v1을 루트로 v2 합치기
}

 

2, 풀이 중점 사항

 

각 도시로 연결되는 간선은 양방향 이동 경로 입니다. 이는 곧 주어지는 n개의 줄은 대칭 형태로 주어지고 있습니다.

저는 대각선을 기준으로 오른쪽에 위치한 값으로 parent 와 child를 설정하였습니다.

col > row 인 조건에서 link == 1 이라면, row가 부모가 되어, child를 연결할 수 있도록 구성하였습니다.

 

if (col > row) { // 링크가 연결되어 있다면 row의 도시 번호를 기준으로 합치기
    if (link == 1) union(find(row), find(col));
}

 

이 코드의 효과로, 1 -> 2가 연결되어 있다면 root 노드가 1이 되고, 2는 루트가 1인 집합의 원소가 됩니다.

이어지는 값에서 2 -> 3으로 연결된다면, 2는 root가 1이므로 3은 root 1을 그대로 따르게 됩니다.

 

static boolean isSameRoot() {
    
    if (m == 0) return true; // 만약 들려야 하는 도시가 0이라면 종료
    boolean check = true; // 루트가 같은지 판단
    
    int root = find(nodes.get(0));
    for (Integer node : nodes) {
        if (!(root == find(node))) { // 루트가 다르다면 간선이 존재하지 않음
            check = false;
            break;
        }
    }
    
    return check;
}

 

해당 소스에서 nodes.get(0)으로 꺼낸 root의 값이 거쳐야 하는 도시들의 root와 다르다면, 이는 다른 도시들을 경유하여 갈 수 없는 경로임을 의미하므로 false를 리턴하였습니다. 만약 거쳐야 하는 도시가 모두 root를 따른다면, 양방향 간선으로 인해, 서로 도시 간 이동이 가능합니다.

 

이상으로 유니온 파인드 문제 여행 가자 자바 풀이를 마치도록 하겠습니다.!

감사합니다.!