[BOJ] 1976. 여행 가자 - JAVA

🔗 문제

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

1976번: 여행 가자

 

🧩 풀이 및 코드

문제 유형 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합

 

내가 푼 방법은 Floyd 를 사용한 것이었는데, 출발지와 도착지가 같다면 여행할 수 있다는 것을 생각해내지 못해서 틀렸다. 검색을 하다가 Floyd는 시간 복잡도가 O(N^3) 이고 대부분 Union-Find 를 사용해서 푼 것 같아 2가지 방법으로 풀었다.

 

Floyd (메모리, 시간, 코드 길이 순서)

Union-Find

Union-Find 에서 union 할 때 parent[x] = y; 에서 x 를 x 의 부모로 해야 하는 것에서 조금 헤맸다.

 

1) 전체 코드 - Floyd

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

public class Main_bj_1976_여행가자 {

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_1976.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int tripN = Integer.parseInt(br.readLine());
		
		int[][] graph = new int[N+1][N+1];
		
		final int INF = 987654321;
		
		StringTokenizer st;
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=1; j<=N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
				if(i==j) graph[i][j] = 1; 		// 출발점과 도착점이 같다면 항상 여행이 가능함
				if(graph[i][j] == 0) graph[i][j] = INF;
			}
		}
		
		// Floyd
		for(int k=1; k<=N; k++) {			// 경
			for(int i=1; i<=N; i++) {		// 출
				for(int j=1; j<=N; j++) {	// 도
					if(graph[i][j] > graph[i][k] + graph[k][j]) {
						graph[i][j] = graph[i][k] + graph[k][j];
					}
				}
			}
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		int from = Integer.parseInt(st.nextToken());	// 첫 번째 출발 도시
		
		boolean isPossible = true;
		for(int i=1; i<tripN; i++) {
			int to = Integer.parseInt(st.nextToken());
			
			if(graph[from][to] >= INF) {
				isPossible = false;
				break;
			}
			from = to;
		}
		
		if(isPossible)
			System.out.println("YES");
		else
			System.out.println("NO");
		
		br.close();
	}

}

 

2) 전체 코드 - Union-Find

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

public class Main_bj_1976_여행가자_sol2 {
	
	static int[] parent;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int tripN = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		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 value = Integer.parseInt(st.nextToken());
				
				if(value == 1) {
					union(i, j);
				}
			}
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		int from = Integer.parseInt(st.nextToken());
		boolean isPossible = true;
		for(int i=1; i<tripN; i++) {
			int to = Integer.parseInt(st.nextToken());
			
			if(findParent(from) != findParent(to)) {
				isPossible = false;
				break;
			}
			
			from = to;
		}
		
		if(isPossible) System.out.println("YES");
		else System.out.println("NO");
		
		br.close();
	}
	
	static int findParent(int n) {
		if(parent[n] == n) return n;
		return parent[n] = findParent(parent[n]);
	}
	
	static void union(int from, int to) {
		int fromParent = findParent(from);
		int toParent = findParent(to);
		
		if(fromParent == toParent) return;
		
		if(fromParent < toParent) parent[toParent] = fromParent;
		else parent[fromParent] = toParent;
	}
}

 

---

Reference

https://steady-coding.tistory.com/109

[BOJ] 백준 1976번 : 여행 가자 (JAVA)