[백준] 1976 여행 가자 - 유니온 파인드(Union Find) JAVA

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

코드설명

유니온 파인드(Union Find) 문제입니다.

 

각 정점들이 같은 그래프내에 있는지만 확인하면 되기에 유니온 파인드를 활용하여 해당 그래프들이 같은 그룹에 있는지 확인합니다.

 

유의해야하는점은

//int ParentValue = parent[plan[0] - 1];
int ParentValue = findParent(plan[0] - 1);
 
for(int i=1;i<M;i++) {
//if(ParentValue != parent[plan[i] - 1]) {
    if(ParentValue != findParent(plan[i] - 1)) {
        System.out.println("NO");
        return ;
    }
}

• Parent[] 를 통해 접근하면 정답이 아니고, findParent를 통해 접근해야만 올바르게 통과합니다.
• 물론, findParent를 통해서 Parent값을 갱신하며 진행할 수 있지만, 왜 Parent로 접근하여 비교한다면 올바른 정답이 아닌것인가라는 의문이 생깁니다. Parent[i] 로 접근하나, findParent[i]로 접근하나 결과값은 동일하다고 생각할 수 있습니다.
• 하지만, 만약 더 낮은 Index의 값이 나중에 들어왔다고 할경우 이전에 unionParent한 값의 parent배열은 변경되지 않으므로 새롭게 findParent를 통해 parent를 갱신시켜야합니다.

 

또한 추가로, 시간을 더 감소시키기 위해서

for(int i=1; i<=N;i++) {
    st = new StringTokenizer(br.readLine());
    for(int j=1; j<=i;j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
        if(arr[i][j] == 1) {
            unionParent(i, j);
        }
    }
}

입력으로 주어진 도시의 연결정보에서 대각선 기준으로 대칭모양이므로 위와 같이 j<=i 로만 처리하여 중복결과를 피할 수 있습니다.

0 1 0
1 0 1
0 1 0

 

정답을 구할때는 처음에 주어진 여행게획을 Parent Value로 입력받고, 그 이후에 여행계획들이 Parent Value와 다르다면 같이 분리집합이 아니므로 실패처리합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[][] arr;
	public 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());
    	
    	arr = new int[N+1][N+1];
    	parent = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=1; i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1; j<=i;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    			if(arr[i][j] == 1) {
    				unionParent(i, j);
    			}
			}
    	}
    	
    	
    	for(int i=1; i<=N;i++) {
    		findParent(i);
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	int storeParent = parent[Integer.parseInt(st.nextToken())];
    	for(int i=2;i<=M;i++) {
    		if(storeParent != parent[Integer.parseInt(st.nextToken())]) {
    			System.out.println("NO");
    			return ;
    		}
    	}
    	System.out.println("YES");
    	
	}
    
    public static int findParent(int x) {
    	if(x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	
    	if(a < b) {
    		parent[b] = a;
    	}else {
    		parent[a] = b;
    	}
    }
    
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static int[][] arr;
	public static int[] plan;
	
	public static int[] parent = new int[201];
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b ) parent[b] = a;
		else parent[a] = b;
	}
	
    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());
    	
    	arr = new int[N][N];
//    	parent = new int[N];
    	
    	for(int i=0;i<N;i++) {
    		parent[i] = i;
    	}
    	
//    	for(int i=0;i<N;i++) {
//    		System.out.print(" "+parent[i]);
//    	}
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		
    		for(int j=0;j<=i;j++) {
    			
    			if(arr[i][j] == 1) {
    				unionParent(i, j);	
    			}
    			
    		}
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	plan = new int[M];
    	
    	for(int i=0;i<M;i++) {
    		plan[i] = Integer.parseInt(st.nextToken());
    	}
    	if( M < 0) System.out.println("YES");
    	
//    	int ParentValue = parent[plan[0] - 1];
    	int ParentValue = findParent(plan[0] - 1); // //만약 더 낮은 Index의 값이 나중에 들어왔다고 할경우 이전에 unionParent한 값의 parent배열은 변경되지 않으므로 새롭게 findParent를 통해 parent를 갱신시켜야합니다.
    	 
    	for(int i=1;i<M;i++) {
//    		if(ParentValue != parent[plan[i] - 1]) {
    		if(ParentValue != findParent(plan[i] - 1)) { // //만약 더 낮은 Index의 값이 나중에 들어왔다고 할경우 이전에 unionParent한 값의 parent배열은 변경되지 않으므로 새롭게 findParent를 통해 parent를 갱신시켜야합니다.
    			System.out.println("NO");
    			return ;
    		}
    	}
    	System.out.println("YES");
    }
}