SH

https://www.acmicpc.net/problem/1197 MST 기본 문제 (크루스칼 사용함)  가중치 오름차순 정렬된 edges를 순회하며,  V-1개의 간선을 만들면 종료한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer;class Main { static class Edge impl..

https://www.acmicpc.net/problem/24391 유니온-파인드를 통해 분리 집합을 구성하고,주어진 경로를 탐색하며 부모(== 분리 집합 대표자)가 바뀐 횟수를 구하는 문제다. 단, 첫 원소 (맨 처음 강의를 들으러 이동)는 세지 않는다. 간만에 푸는 문제 분류라 첫 ac에 빵꾸가 많았다. 이후 수정해서 700 -> 400ms로 줄였다. 1. find에서 좌표 압축2. parent 최신화하고 탐색 -> find()로 탐색3 priority 배열 제거(문제에서 강의 순서가 존재한다. 유니온 대표자를 정하는 기준으로 사용했는데, 결과적으로 불필요했다.)4. 간선(edge)안만들고 바로 union (심지어 양방향으로 만들어서 union 두 번씩 함)5. path 배열 제거 이전 코드더보기im..