백준 | 1976번. 여행 가자 - 유니온 파인드

⬛ 백준 1976번. 여행 가자 - 유니온 파인드 

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

1976번: 여행 가자

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

💚나의 풀이

• 동혁이가 가려고 하는 여행 경로는 M개로 구성되어 있다는 점에 주의하자.
• 우선 인접행렬로 i→j를 향하는 연결 정보가 1인 값에 대하여 parent[]배열에서 union(i, j) 시켜준다.
• 그리고 나서 동혁이의 M개 여행 계획 도시의 각 부모 노드가 모두 같은 부모 노드를 지칭한다면 같은 집합이므로 “가능” 한 상태이고, 하나라도 다른 부모 노드를 갖는 애가 나타난다면 “불가능” 한 것이므로 NO를 출력하도록 짰다.
• route[1]의 부모를 find(route[1]) 로 찾아서 int형 변수에 담아두고 for문으로 2 ~M까지 돌면서 1의 부모와 다른 애가 나타나는지 모두 같은지 그 여부를 확인하면 되는 문제였다.

import java.util.Scanner;

/*1976번. 여행 가자 - 유니온 파인드 */
public class Main {
	static int n, m; //m은 여행계획속도시수 
	static int[] parent;
	static int[][] map;
	static int[] route;//계획한 여행 도시 담기 - m개
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		map = new int[n+1][n+1];
		parent = new int[n+1];
		//parent 초기ㅗ하
		for(int i=1; i<=n; i++) parent[i]= i;
	
	
		//입력받기 
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		route = new int[m+1];//얘 도시 계획 담긴 배열 
		//동혁이의 여행 계획 담기 
		for(int i=1; i<=m; i++) route[i]= kb.nextInt();
		
		//이제 각 map 돌면서 1인 값에 대해서는 union 처리 
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == 1) {
					union(i, j);//경로 합치기 
				}
			}
		}
		
		//이제 각 도시별 부모 도시 찾아서 하나라도 다른 도시 나오면 X 모두 같으면 O
		
		//첫번째 도시의 부모는 미리 찾아둠 
		int tmp = find(route[1]);
		
		for(int i=2; i<route.length; i++) { //그 뒷쪽 루트도시의 부모도시가 하나라도 1번이랑 다르다면 
			if(tmp != find(route[i])) { //뒷 부분 루트 순회하면서 
				//하나라도 1번의 부모와 다른 부모 나타나면 
				System.out.println("NO"); //안속해 있음
				return;//걍 여기서 끝 
			}
		}
		//아니라면 탈출해서 YES
		System.out.println("YES");
	}
}