[1976] 여행 가자 - Java[자바]

 

| 문제 링크

 

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

1976번: 여행 가자

 

 

 

---

 

 

 

| 문제

 

1. 첫째 줄에 n개의 도시가 있고, m개의 도시를 여행하고자 합니다.
2. n개의 줄에 n개의 숫자(0 or 1)각 주어집니다.
3. i번째 줄은 i번째 도시를 뜻하며, 해당 줄에 j번째 숫자는 j번째 도시를 의미합니다.
   0은 연결되지 않음 1은 연결됨
4. 마지막 줄에 m개의 숫자(도시)가 나오며, 해당 도시들을 여행할 수 있으면(연결된 도시들을 몇 개를 거쳐가든 괜찮습니다.)  YES, 여행할 수 없으면 NO를 출력하시오

 

 

 

---

 

 

 

| 풀이

 

1. 여행하고자 하는 도시들이 연결되어 있는지 확인을 해야합니다.
2. 각 노드(도시)들의 공통 조상(그래프에 속한 노드들 중 낮은 숫자를 조상으로 설정)을 구해 모두 같은 경우 YES, 다른 경우에는 NO를 출력하는 문제입니다.
3. 각 노도들의 공통 조상을 구하기 위해 유니온 파인드 알고리즘을 사용합니다.
4. 우선 각 노들들의 조상을 자기 자신으로 설정합니다.
5. 입력값으로 두 도시(a, b라 설정)가 연결된 경우(1이 들어오는 경우) a와 b의 조상 노드를 확인해 더 낮은 조상 노드로 바꾸며 입력값을 전부 확인합니다.
6. 여행하고자 하는 도시들의 조상 노드가 동일한 경우 YES, 아닌 경우 NO를 출력합니다.

 

 

 

---

 

 

 

 

| 코드

 

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

public class Main {

	public static int[] parent;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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++) {
				int node = Integer.parseInt(st.nextToken());
				//도시끼리 길이 이어져 있을 경우 조상을 하나로 통일한다.
				if (node == 1)
					union(i,j);
			}
		}

		//방문 하고자 하는 도시들의 조상이 같은 경우에는 어떤 경로를 거치든 방문이 가능하나
		//조상이 다른 경우에는 이동할 수 없다. 즉 도시 하나씩 조상을 꺼내어 비교해 다 같은 경우 YES, 다른 경우 NO 출력
		st = new StringTokenizer(br.readLine());
		String answer = "YES";
		int top = top(Integer.parseInt(st.nextToken()));
		while(st.hasMoreTokens()) {
			int top2 = top(Integer.parseInt(st.nextToken()));
			if(top!=top2) {
				answer="NO";
				break;
			}
		}
		bw.write(answer);
		br.close();
		bw.close();
	}
	
	//해당 노드의 조상을 불러와서 공통된 조상인 경우 이동이 가능하다 판단
	public static int top(int a) {
		if(a==parent[a])
			return a;
		parent[a]=top(parent[a]);
		return parent[a];
	}
	
	//a와 b가 이어져 있을 경우 조상을 통일해 준다. 이때 숫자가 더 낮은 조상이 조상이 되는게 국룰이다.
	public static void union(int a, int b) {
		int topA = top(a);
		int topB = top(b);
		
		//a보다 b가 큰 경우 b의 조상은 a의 조상
		if(topA<topB)
			parent[topB]=topA;
		else
			parent[topA]=topB;
	}

}