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

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

1976번: 여행 가자

 

 

Disjoint - Set 알고리즘 분류 문제인데

 

일반적인 방법으로 풀었다.

 

 

두 가지 전부 작성하겠다.

 

 

우선, 이 문제의 중점은

 

"경로 중복 가능하고, 이전 경로를 되돌아갈 수 있다."

 

는 것이다.

 

 

기존의 그래프 문제(특히, 다익스트라 같은) 들은 대부분 중복된 경로를 허용하지 않는다.

 

그렇기때문에 다른 알고리즘을 사용하는 것이고.

 

 

하지만 여기서는 반대로 가능하기 때문에

 

Disjoint - Set도 가능하다.

 

 

우선 제가 푼 첫 번째 방법은

 

"해당 지점에 도착한 적이 있으면 무조건 방문할 수 있다."

 

를 활용했다.

 

 

 

그렇기 때문에 해당 지점에서 출발하는 모든 경우의 수를 구해 방문 체크를 한다.

당연히 boolean 배열로 중복 방문을 제거한다.

*** 안그러면 두 점만 왔다갔다 할 수 있다..

 

다음, 입력받은 경로를 하나씩 까보며

 

 

방문 X(False)가 있으면 바로 불가능

하나라도 False가 없으면(전부 True) 가능

 

 

으로 정답을 얻을 수 있다.

 

쉽게 풀 수 있다.

 

 

 

그럼 두 번째

Disjoint - Set 은 어떻게 사용했나?

*** 참고로 위 첫 번째 방법과 시간과 용량은 비슷했다.

 

 

두 지점을 입력받으면

 

  1)  두 지점을 Union을 한다.

*** 이 때, 두 번 하는 것을 방지해야한다. 즉, (2, 3) 과 (3, 2) 를 입력받기 때문에 하나만 Union할 수 있도록 해야함

 

  2)  모든 경로의 Find() 값이 같으면 전부 같은 경로선상(동일선상)에 있다는 뜻이므로 정답

       하나라도 다르면 같은 경로선상이 아니므로 오답

 

 

 

쉽다.

 

쉬운데 아직은 Union - Find 사용 방법을 잘 모르겠다.

 

응용할 수 있는 범위가 넓어서 그런가?

 

 

 

 

따라서, 별도 매커니즘은 작성하지 않겠습니다!

 

소스코드 참고해주세요!

 

감사합니다.

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	// 여행 가자
	// Disjoint - Set ?
	public class p1976 {
	static int[][] map;
	static ArrayList<Integer>[] graph;
	static ArrayList<Integer> route;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.parseInt(st.nextToken());
	int m = Integer.parseInt(br.readLine());
	route = new ArrayList<Integer>();
	graph = new ArrayList[n + 1];
	for(int i = 1; i <= n; i++) {
	graph[i] = new ArrayList<Integer>();
	}
	// Input 넣기
	for(int i = 1; i <= n; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j = 1; j <= n; j++) {
	int num = Integer.parseInt(st.nextToken());
	if(num == 1) {
	graph[i].add(j);
	}
	}
	}
	st = new StringTokenizer(br.readLine());
	while(st.hasMoreTokens()) {
	int dest = Integer.parseInt(st.nextToken());
	route.add(dest);
	}
	String print = possibleRoute(n, route.get(0)) ? "YES" : "NO";
	System.out.println(print);
	}
	static boolean possibleRoute(int n, int start) {
	boolean[] visited = new boolean[n + 1];
	Queue<Integer> q = new LinkedList<Integer>();
	q.offer(start);
	while(!q.isEmpty()) {
	int ele = q.poll();
	if(visited[ele]) {
	continue;
	}
	visited[ele] = true;
	for(int i = 0; i < graph[ele].size(); i++) {
	int next = graph[ele].get(i);
	q.offer(next);
	}
	}
	// 경로에 한 번이라도 방문한 적이 있는지 파악하기
	// 중복 경로가 가능하고, 이전 길로도 되돌아갈 수 있어서 한 번이라도 방문했으면 어떤 순서건 간에 방문할 수 있다.
	for(int dest : route) {
	if(visited[dest]) {
	continue;
	}
	return false;
	}
	return true;
	}
	}

view raw p1976.java hosted with ❤ by GitHub