[백준] 여행가자 1976 [JAVA]

출처 : 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 행렬을 통해 임의의 두 도시가 연결되었는지에 관한 정보가 주어진다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다.

출력

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

풀이방법

1) union- find 

2) 큐를 사용한 Union-Find 

헷갈렷던 점

1. union 하는 과정에서 parents[px] = py ; 면 될 줄 알았는데 큐를 사용하는 과정에서 px = py 할지, py=px에 따라 정답이 바뀌었다.

2. 마지막에 같은 집합인지 비교하는 과정에서 최종 부모의 도시를 가져왔어야 했는데, 중간 도시를 가져와서 틀렸다.

Union-Find Using Queue

package 알고리즘공부하기;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 여행가자_1976 {

	static int parents[];
	static int n, m;
	static int[][] city;
	static boolean[] visited;
	static int[] journey;
	static String answer = "YES";
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); // 총 도시의 수
		m = sc.nextInt(); // 여행 계획에 속한 도시의 수 
		
		// 초기화
		parents = new int[n+1];
		visited = new boolean[n+1];
		journey = new int[m];
		city = new int[n+1][n+1];
		for( int i=1; i<=n; i++) {
			parents[i] = i; // 1부터 시작
		}
		
		// 입력 받기
		for( int i=1; i<=n; i++) {
			for( int j=1; j<=n; j++) {
				city[i][j] = sc.nextInt();
			}
		}
		
		for( int i=0; i<m; i++) {
			journey[i] = sc.nextInt();
		}
		
		// 1. 각 도시로 부터 이동 가능한 도시들을 하나의 집합으로 묶자.
		for( int i=1; i<=n; i++) {
			// 본인 도시 == 도시 라면 city 만들기
			if( !visited[i]) {				
				makecity(i);
			}
			
		}
		
		// 2. 여행 계획의 도시들이 같은 집합이라면 Yes, 아니라면 NO
		for( int i=0; i<m; i++) {
			int Metro = parents [ journey[0] ];
			if ( Metro != parents [ journey[i] ]) {
				answer = "NO";
			}
		}
		
		System.out.println(answer);
				
	}
	private static void makecity(int start) {
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		
		while( !queue.isEmpty()) {
			int S = queue.poll();
			
			for( int target = 1; target <= n; target++) {
				// 갈 수 있는 곳이라면, 방문하지 않았다면
				if( city[S][target] == 1 && !visited[target]) {
					visited[target] = true; // 방문표시
					// 큐에 추가
					queue.add(target);
					// 같은 집합으로 묶기
					//print();
					union(S,target);
					//System.out.println("=====union=========");
					//print();
					//System.out.println();
				}
				
			}
		}
	}
	private static void print()	{
		for( int i=1; i<parents.length; i++) {
			System.out.print(parents[i]+" ");
		}
	}
	
	private static void union(int x, int y) {
		int px = getParent(x);
		int py = getParent(y);
		
		if ( px == py ) return;
		else {

			 parents[py]= px;
		}
		
		
	}

	private static int getParent(int x) {
		if ( parents[x] == x ) return x;
		return parents[x] = getParent( parents[x] );
	}
	
}

Only Union-Find

package 알고리즘공부하기;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 여행가자_1976_V2 {
	static int parents[];
	static int n, m;
	static int[][] city;
	static boolean[] visited;
	static int[] journey;
	static String answer = "YES";

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt(); // 총 도시의 수
		m = sc.nextInt(); // 여행 계획에 속한 도시의 수

		// 초기화
		parents = new int[n + 1];
		visited = new boolean[n + 1];
		journey = new int[m];
		city = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			parents[i] = i; // 1부터 시작
		}

		// 입력 받기
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				city[i][j] = sc.nextInt();
				if ( city[i][j] == 1) {
					union(i,j);
				}
			}
		}

		for (int i = 0; i < m; i++) {
			journey[i] = sc.nextInt();
		}


		// 2. 여행 계획의 도시들이 같은 집합이라면 Yes, 아니라면 NO
		for (int i = 0; i < m; i++) {
			int Metro = getParent(parents[journey[0]]);
			if (Metro != getParent(parents[journey[i]])) {
				answer = "NO";
			}
		}

		System.out.println(answer);

	}

	private static void makecity(int start) {

		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);

		while (!queue.isEmpty()) {
			int S = queue.poll();

			for (int target = 1; target <= n; target++) {
				// 갈 수 있는 곳이라면, 방문하지 않았다면
				if (city[S][target] == 1 && !visited[target]) {
					visited[target] = true; // 방문표시
					// 큐에 추가
					queue.add(target);
					// 같은 집합으로 묶기
					// print();
					union(S, target);
					// System.out.println("=====union=========");
					// print();
					// System.out.println();
				}

			}
		}
	}

	private static void print() {
		for (int i = 1; i < parents.length; i++) {
			System.out.print(parents[i] + " ");
		}
	}

	private static void union(int x, int y) {
		int px = getParent(x);
		int py = getParent(y);

		if (px == py)
			return;
		else {
			if ( x < y ) {
				parents[py] = px;
			}
			else {
				
				parents[px]= py;
			}
			//parents[px] = py;
		}

	}

	private static int getParent(int x) {
		if (parents[x] == x)
			return x;
		return parents[x] = getParent(parents[x]);
	}

}

 

* Metro 부분이 좀 다르다.