백준 - 1976 - Java - BFS, 유니온파인드 풀이

1. 문제

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

입력 예제

3
3
0 1 0
1 0 1
0 1 0
1 2 3

출력 예제

YES

2. 풀이

단순히 여행이 가능한지, 불가능한지 체크하면 되기 때문에 BFS로도 가능하고, 유니온파인드로도 가능한 풀이이다.

1. BFS
   Queue에다가 여행계획 중 한 도시를 삽입하고 BFS를 돌면서 visit이 가능한지 확인해준다.

2. 유니온 파인드
   기존 유니온파인드처럼 연결이 되어있을경우 union을 통해서 한 집합으로 만들어주고,
   여행 계획 도시 번호들의 parent값이 같으면 YES, 아니면 NO를 출력하면 된다.

3-1. [BFS] 코드

import java.util.*;
import java.io.*;

public class BFS_1976 {
	
	static boolean visit[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		visit = new boolean[N+1];
		ArrayList<Integer> plans = new ArrayList<>();
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 1; j <= N; j++) {
				if(Integer.parseInt(st.nextToken()) == 1) {
					list.get(i).add(j);
				}
			}
		}
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < M; i++) {
			plans.add(Integer.parseInt(st.nextToken()));
		}
		
		Queue<Integer> q = new LinkedList<>();
		q.add(plans.get(0));
		visit[plans.get(0)] = true;
		
		while(!q.isEmpty()) {
			
			int X = q.poll();
			
			for(int i = 0; i < list.get(X).size(); i++) {
				int nextNode = list.get(X).get(i);
				
				if(!visit[nextNode]) {
					visit[nextNode] = true;
					q.add(nextNode);
				}
			}
		}
		
		for(int i = 1; i < plans.size(); i++) {
			if(!visit[plans.get(i)]) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
}

3-2. [유니온 파인드] 코드

import java.util.*;
import java.io.*;

public class UnionFind_1976 {

	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		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 <= N; j++) {
				if(Integer.parseInt(st.nextToken()) == 1) {
					union(i, j);
				}
			}
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		int checkParent = findParent(Integer.parseInt(st.nextToken()));
		for(int i = 1; i < M; i++) {
			if(checkParent != findParent(Integer.parseInt(st.nextToken()))) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
	
	public static void union(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		
		if(a < b) {
			parent[b] = a;
		} else {
			parent[a] = b;
		}
	}
	
	public static int findParent(int x) {
		if(parent[x] == x) {
			return x;
		} else {
			return parent[x] = findParent(parent[x]);
		}
	}
}