[이것이 코딩 테스트다] 여행계획

문제

문제의 저작권은 ‘이것이 코딩테스트다’ 교재에 있습니다.

한울이가 사는 나라에는 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번의 순서로 여행지를 방문하면 여행 계획을 따를 수 있다. 여행지의 개수와 여행지 간의 연결 정보가 주어졌을 때, 한울이의 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성해라.

입력1

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

출력1

YES

입력2

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

출력2

NO

접근방식

Union-find알고리즘으로 노드들이 서로 연결되어 있는지를 확인한다.

1) 초기에 자기자신을 집합으로 한다. parents[i] = i로 세팅한다.

2) Union(int a, int b) : 간선정보를 입력받으면서 두 노드의 각 부모노드를 합친다.

• Find(a), Find(b)함수를 실행해서 a,b의 최상위 부모노드를 찾는다.
• 두개의 최상위 부모노드 중 더 작은 쪽으로 부모노드를 갱신한다.

3) Find(int x) : 재귀호출 하면서 x의 최상위 부모노드를 찾는다.

• parent[x]==x인 경우 자기자신이 부모노드인 최상위에 도달한 것으로 이때의 parent[x]값을 갱신해주고 return한다.

4) 여행할 노드를 입력받아 inputs배열에 넣고 하나씩 꺼내면서 inputs[i]와 inputs[i+1]이 서로 연결되었는지 확인하기 위해 부모노드가 같은지 확인한다.
⇒ 여기서 하나라도 같지 않으면 flag변수 Ans를 false처리 후 빠져나오고 그에 따른 Yes or No를 출력한다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[] parents; //각 노드의 부모노드 저장
	static int N,M; //정점수, 간선수
	static int[] inputs;
	static boolean Ans;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());	
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		parents = new int[N+1];
		//1. 초기에 자기 자신을 집합으로 한다.
		for(int i=1; i<=N; i++) parents[i] = i;
		
		//2. 각 정점을 연결짓는다.
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());	
			for(int j=0; j<N; j++) {
				int w = Integer.parseInt(st.nextToken());
				if(w == 1) union(i+1, j+1);
			}
		}
		
		//3. 입력받은 정점이 연결되는지 확인한다.
		st = new StringTokenizer(br.readLine());	
		inputs = new int[M];
		
		for(int i=0; i<M; i++) inputs[i] = Integer.parseInt(st.nextToken());
		
		Ans = true;
		for(int i=0; i<M-1; i++) {
			//두 노드의 부모노드가 같으면 연결되어있음을 이용해 연결여부 확인
			if(find(inputs[i]) != find(inputs[i+1])) {
				Ans = false;
				break;
			}
		}
		
		if(Ans) System.out.println("YES");
		else System.out.println("NO");
	}
	
	//a와 b를 합치는데 부모노드가 더 작은 쪽으로 parents[x]값을 갱신한다.
	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a < b) parents[b] = a;
		else parents[a] = b;
	}
	
	//노드의 최상위 부모노드를 찾는다.
	private static int find(int x) {
		if(parents[x] == x) return x;
		else return parents[x] = find(parents[x]);
	}
}