[백준, 13905, G4, MST] 세부

0. 문제 링크

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

13905번: 세부

---

1. 문제 핵심

1. 그래프 탐색을 하며 출발지부터 목적지까지 경로를 탐색하는 중에 가장 빼빼로를 많이 들고갈 수 있는 경로를 탐색하는 문제입니다.

---

2. 문제 접근

그래프 탐색이기 때문에 별 생각없이 다익스트라를 사용했습니다. 다익스트라를 사용했을 때 가지치기를 적절히 사용해준다면 문제는 풀립니다.

풀이 시간은 대략 40분 걸렸습니다.

하지만 자바 1등과 시간 차이가 커서 다른 방법으로 접근해야 한다고 생각이 들었습니다.

PQ를 사용해서 다시 풀었지만 시간이 크게 줄어들진 않았습니다.

 

문제 유형을 보니 MST라고 적혀있어서 크루스칼 방식으로 재시도를 했습니다. (너무 오랫만에 MST라서 크루스칼은 다시 학습했습니다.)

크루스칼 방식은 확실히 조금 더 빠른 것 같았지만 54%에서 막혀 더 이상 진행이 되지 않았습니다.

대체 무엇이 문제인가 싶어 1시간 가량 고민했지만 답이 나오지 않아 질문을 참고했습니다.

조금 충격이었는데 본 문제에는 항상 시작점과 끝점이 이어진 케이스를 제공한다는 문구가 없었고 따라서 금빼빼로를 들고가지 못하는 경우가 있는 것입니다.

끝점과 시작점이 무조건 이어지는 경우에만 해당 빼빼로 개수를 출력하는 코드는 절대 통과할 수 없는 것입니다.

코드를 위와 같이 수정하니 통과할 수 있었습니다.

---

3. 코드 분석

유니온 파인드

 

유니온 파인드를 통한 간선 연결 확인

---

4. 베스트 코드 분석

1. 코드 자체는 제 코드와 크게 다르지 않지만 연결 데이터를 클래스로 관리해주었습니다.

---

5. 코드

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

public class Main {
	static int[] set;

	static boolean Union(int a, int b) {
		a = findSet(a);
		b = findSet(b);

		if (a == b)
			return false;
		else {
			if (set[a] < set[b]) {
				set[a] += set[b];
				set[b] = a;
			} else {
				set[b] += set[a];
				set[a] = b;
			}
			return true;
		}
	}

	static int findSet(int a) {
		// 음수라면 루트
		if (set[a] < 0)
			return a;
		return set[a] = findSet(set[a]);
	}

	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(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int s = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o2[2] - o1[2]);
		int start, end, weight, answer = 0;
		
		set = new int[N + 1];
		Arrays.fill(set, -1);

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			weight = Integer.parseInt(st.nextToken());
			q.add(new int[] { start, end, weight });
		}

		int[] crnt;
		while (!q.isEmpty()) {
			crnt = q.poll();
			if (Union(crnt[0], crnt[1])) {
				// 시작과 끝이 이어졌을 때
				if (findSet(s) == findSet(e)) {
					answer = crnt[2];
					break;
				}
			}
		}
		System.out.println(answer);
	}
}