그래프 이론 - 1. 여행 계획

문제

한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1~N번까지의 번호로 구분된다.
또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있다.
이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미이다.
한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 한다.

여행지의 개수와 여행지 간의 연결 정보가 주어졌을 떄, 한울이의 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하세요.

예를 들어 N = 5이고, 다음과 같이 도로의 정보가 주어졌다고 가정하자.

• 1번 여행지 - 2번 여행지
• 1번 여행지 - 4번 여행지
• 1번 여행지 - 5번 여행지
• 2번 여행지 - 3번 여행지
• 2번 여행지 - 4번 여행지

만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3 번이라고 해보자.
이 경우 2번 -> 3번 -> 2번 -> 4번 -> 2번 -> 3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있다.

입력 조건

• 첫째 줄에 여행지의 수 N과 여행 계획에 속한 도시의 수 M이 주어진다.(1 <= N, M <= 500)
• 다음 N개의 줄에 걸쳐 N * N 행렬을 통해 임의의 두 여행지가 서로 연결되어 있는지의 여부가 주어진다. 그 값이 1이라면 서로 연결되었다는 의미이며, 0이라면 서로 연결되어 있지 않다는 의미이다.
• 마지막 줄에 한울이의 여행 계획에 포함된 여행지의 번호들이 주어지며 공백으로 구분한다.

출력 조건

• 첫째 줄에 한울이의 여행 계획이 가능하다면 YES, 불가능하다면 NO를 출력한다.

입력 예시

5 4
0 1 0 1 1
1 0 1 1 0
0 1 0 0 0
1 1 0 0 0
1 0 0 0 0
2 3 4 3

출력 예시

YES

구현코드

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

public class Main{

	public static int n;
	public static int m;
	public static int[] parent;
	
	public static int findParent(int a){
		if(a == parent[a]) return a;
		else return parent[a] = findParent(parent[a]);
	}
	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());
		m = Integer.parseInt(st.nextToken());
		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++){
				int a = Integer.parseInt(st.nextToken());
				if(a == 1) unionParent(i ,j);
			}
		}
		st = new StringTokenizer(br.readLine());
		boolean check = true;
		int k = parent[Integer.parseInt(st.nextToken())];
		for(int i = 1 ; i < m ; i++ ){
			if(k != parent[Integer.parseInt(st.nextToken())]) {
				check = false;
				break;
			}
		}
		if(check) System.out.println("YES");
		else System.out.println("NO");
	}
}

코드해석

여행계획 문제는 같은 집합에 있는지 없는지를 물어보는 문제이다. 예행계획이라고 포장해두었지만 요구하는 사항은 마지막에 주어진 노드들의 부모노드들이 같은지 아닌지를 물어보는 문제이다.