[JAVA]백준 9372번: 상근이의 여행

 

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

9372번: 상근이의 여행

 

 

 

 

| 문제 해결방법

 

 

⭐Idea : 크루스칼 알고리즘 ( '가장 적은 간선으로 모든 노드를 연결하는 방법' 을 구하기 )

 

 

 

크루스칼 알고리즘은 모든 간선을 연결하는 최소 비용을 구할 때 사용한다. 

 

 

각 간선의 크기가 주어진 경우라면,

간선의 크기로 오름차순 정렬을 해준 후 정렬된 순서대로 간선을 연결한다.

 

 

✔ 하지만 이 문제는 간선의 크기가 없어서 간선의 크기는 고려하지 않아도 된다.
   (서로소 집합과 크루스칼 알고리즘을 처음 이해하는데 도움이 될만한 문제) 
   

 

 

| 진행 순서

1. 간선이 들어오는 순서대로 검사

2. isSameParent()로 입력받은 두 노드의 부모가 같은지 검사

3. ( true )같다면 pass, ( false )다르다면 간선수 +1 and 두 노드 union()

 

 

 

[JAVA] 해설 코드

package week11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_9372 {

	static int E,V, length;
	static int [] parent;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 0;tc < T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			E = Integer.parseInt(st.nextToken());
			V = Integer.parseInt(st.nextToken());
			
			parent = new int[E+1];
			length = 0;
			for(int i=0;i<parent.length;i++) {
				parent[i]=i;
			}
			
			for(int i=0;i<V;i++) {
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				
				// 부모가 같지 않다면
				if(!isSameParent(s, e)) {
					// 간선을 연결하고 간선 수 +1
					length++;
					// 두 노드 합치기
					union(s,e);
				}
				
				// 부모가 같으면 어떠한 동작도 하지 않고 다음으로 넘어감
				
			}
			
			System.out.println(length);
		}

	}
	// 간선 연결
	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a != b) {
			parent[b] = a;
		}
	}
	// 부모 노드 찾기 
	private static int find(int a) {
		if(parent[a] == a) {
			return a;
		}
		return parent[a] = find(parent[a]);
	}
	// 부모가 같은지를 판별해주는 method
	private static boolean isSameParent(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a==b) return true;
		else return false;
	}
}

 

[제출] 메모리 및 시간

 

✔ BFS를 사용해도 풀리긴 하지만 크루스칼 알고리즘이 메모리와 시간측면에서 유리