[백준(Baekjoon)][자바(java)] 1976 : 여행 가자 / 유니온 파인드

 

www.acmicpc.net/problem/1976

1976번: 여행 가자

 

문제 풀이

 

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

public class Main {
	
	public static int find( int x, int p[] ) {
		if( x == p[x] ) 
			return x;
		return p[x] = find( p[x], p );
	}
    
	public static void union( int a, int b, int p[] ) {
		if( a == b )  return;
		a = find( a, p );
		b = find( b, p );
		if( a == b )  return;
		p[b] = a;      
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int n = Integer.parseInt( br.readLine() ), 
		    m =  Integer.parseInt( br.readLine() ), i, j;
		int p[] = new int[n], e, c_p, c_n;	// edge, course prev/next
		for( i = 0; i < n; i++ )
			p[i] = i;
		StringTokenizer st; 
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < n; j++ ) {
				e = Integer.parseInt( st.nextToken() );
				if( e == 1 )
					union( i, j, p );
			}
		}
		String res = "YES";
		st = new StringTokenizer( br.readLine() );
		c_p = find( Integer.parseInt( st.nextToken() ) - 1, p );
		for( i = 1; i < m; i++ ) {
			c_n = find( Integer.parseInt( st.nextToken() ) - 1, p );
			if( c_p != c_n ) {
				res = "NO";
				break;
			}
			c_p = c_n;
		}
		br.close();
		
		System.out.println( res );
		
	}
}

 

*  유니온 파인드

-  N * N 행렬을 입력받으면서 도시 간 연결  --  두 도시를 합침  ( Union 연산 수행 )
-  마지막 줄의 경로를 입력받으면서 이전의 도시와 현재의 도시가 연결되어 있는지 확인  ( Find 연산 수행 )
   --  같은 집합인지 확인 후 같은 집합이면 YES, 다른 집합이면 가능한 경로가 아니므로 NO 출력 

 

( hyunjiishailey.tistory.com/283 )