[BOJ_1976] 여행가자 (골드4) - JAVA

---

🐾 알고리즘

• Union - Find : 서로소 집합을 이용해서 풀기!
• 이 외에도 bfs, 플로이드-워샬 알고리즘을 활용해 풀이 가능

 

---

🐾 생각 포인트

• 6번정도 메모리초과와 런타임에러가 났는데, 오류를 수정하느라 한참 고민했다.  오류가 난 곳은 다름아닌 union method, 여기서 find(x)를 x로 정의하고 find(y)를 y로 재정의한 것이 문제였다. ㅠㅠ 그 원인을 쉽게 찾을 수 없어 챗지피티에게 물어보았다.

private static void union(int x, int y) {
//		x = find(x);
//		y = find(y);
//		
//		if (x > y)
//			parent[x] = y;
//		parent[y] = x;

직접 비교하면 잘못된 결과가 나올 수 있다는 점,, 이는 유니온 파인드 알고리즘시 흔한 실수 중 하나라는 점,, 명심 또 명심

 

---

경로 압축(Path Compression)은 find 함수가 호출될 때 해당 노드부터 루트까지의 경로 상의 모든 노드의 부모를 직접 루트로 만들어주는 기술입니다. 이렇게 하면 같은 집합에 속한 노드들이 더 짧은 경로로 루트에 도달할 수 있게 되어, find 함수의 호출 시간을 줄일 수 있습니다.

그러나 x = find(x);와 같이 직접 x를 루트로 만들면서 할당하게 되면, find 함수 내부에서의 재귀 호출이 사라지게 됩니다. 재귀 호출이 없다는 것은 경로 압축을 적용하지 않았다는 것이며, 이는 find 함수를 여러 번 호출할 때마다 항상 루트에 도달하는 데 더 많은 시간이 소요될 수 있다는 것을 의미합니다.

By Chat GPT

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

해당 반례에서 무한으로 빙빙 돌며 스택오버플로우 현상 확인

---

---

🐾 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main_1976 {
	static int[] parent;
	static int N, M;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine()); // 도시의 수
		M = Integer.parseInt(br.readLine()); // 여행계획에 속한 도시들의 수

		parent = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			parent[i] = i;
		}

		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < N + 1; j++) {
				int num = Integer.parseInt(st.nextToken());
				// 두 도시가 연결되어있으면, 부모를 하나로 통일시키자! (유니온)
				if (num == 1)
					union(i, j);
			}
		}

		// 여행계획
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		for (int i = 1; i < M; i++) {
			int now = Integer.parseInt(st.nextToken());
			if (find(start) != find(now)) {
				// 시작점과 그 후가 이어져있지 않으면 여행불가능
				bw.write("NO\n");
				bw.flush();
				bw.close();
				br.close();
				return;
			}
		}

		bw.write("YES\n");
		bw.flush();
		bw.close();
		br.close();
	}

	// 최상위 부모(대표)찾기
	private static int find(int x) {
		if (x != parent[x])
			 return parent[x] = find(parent[x]);
		return x;

	}

	// 도시 연결하기
	private static void union(int x, int y) {
//		x = find(x);
//		y = find(y);
//		
//		if (x > y)
//			parent[x] = y;
//		parent[y] = x;
		int a = find(x);
		int b = find(y);

		if (a > b) {
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}
}

---

😵‍💫 공부해야 할 점

• 유니온파인드 단순 암기가 아닌 이해해서 풀것... 
• 자꾸 암기로 이어진다... ㅠㅠ 원리를 이해하자