[BOJ] 1976. 여행 가자

유니온 파인드를 이용하는 문제이다.

이차원 배열상 서로 연결되어있다고 표시된 지역은 merge(union)함수를 이용하여 서로 부모를 맞추어주는 작업을 끝낸다음 마지막에 find를 이용하여 모든 여행지점이 같은 부모를 같는지 확인하는 방식으로 풀이하였다.

package boj1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1976_여행가자_2 {
    static int N;
    static int[][] map;
    static int[] p;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        p=new int[N];
        int M=Integer.parseInt(br.readLine());
        int[] arr=new int[M];
 
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++)
            arr[i]=Integer.parseInt(st.nextToken())-1;
        
        func();
        boolean possible=true;
        
        int standard=find(arr[0]);
        for(int i=1;i<M;i++) {
            if(standard!=find(arr[i])) {
                possible=false;
                break;
            }
        }
        if(possible==true)
            System.out.println("YES");
        else
            System.out.println("NO");
        
    }
    
    static void func() {
        for(int i=0;i<N;i++)
            p[i]=i;
        
        
        for(int i=0;i<N;i++) {
            for(int j=i+1;j<N;j++) {
                if(map[i][j]==1) {
                    merge(i,j);
                }
            }
        }
        
    }
    
    
    static void merge(int num1,int num2) {
        num1=find(num1);
        num2=find(num2);
        
        if(num1>num2)
            p[num2]=num1;
        else
            p[num1]=num2;
    }
    
    static int find(int num) {
        if(p[num]==num)
            return num;
        
        return p[num]=find(p[num]);
    }
}