[Munsik] MUNSIK BLOG [Munsik]

문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com풀이간선 관리를 쉽게 하기 위해 2차원 배열을 만들기 보다는 Edge 클래스를 선언해서 List로 관리를 했다. 가중치 기준 오름차순 정렬을 위해 Comparable 인터페이스를 implement하고 compareTo 메서드를 오버라이딩했다. 처음 제출한 코드가 시간초과에 걸려서 BufferedReader와 BufferedWriter를 쓰기는 했는데, 경로 단축을 안해서 시간 초과가 발생했던 것이라서 그냥 Scanner를 사용해도 되지 않았을까 싶다.import java.io.BufferedReader;import java.io.BufferedWriter;impo..

🧩 Union-Find란?Union-Find는 A와 B가 이미 같은 그룹인지 확인하고 아니면 같은 그룹으로 합치는 기능이다. Kruskal 알고리즘에서는 Union-Find를 이용해 새로운 간선을 선택했을 때 사이클이 생기는 판별한다.find(x)x가 속한 그룹의 대표를 찾는다. 예를 들어 {1, 2, 3}이라는 그룹의 대표가 1이라면find(1) = 1find(2) = 1find(3) = 1이 된다.union(a, b)a가 속한 그룹과 b가 속한 그룹을 하나로 합친다. 예를 들어 그룹 1 = {1, 2}이고 그룹 2 = {3}일 때 union(2, 3)을 실행하면 {1, 2, 3}이 된다.root 배열각 그룹이 트리 구조라고 가정해 보자. 여기서 root는 각 노드가 속한 그룹이 어떤 노드를 트리의 ..

🧩 MST란?MST(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프에서 선택한 간선들의 가중치 합이 최소가 되도록 하는 트리다. 위 말을 쉽게 풀어서 쓰자면 "모든 장소를 연결하되 비용이 가장 적게 드는 연결 방법"이다.마을에 도로를 만든다면?A, B, C, D 마을 사이를 잇는 도로의 공사비가 다음과 같다고 하자.일반적인 공사 담당자라면 네 마을 중 어디서 출발해도 서로 갈 수 있게 도로를 만들되, 도로 공사비는 최대한 적게 쓰고 싶을 것이다. 우선 모든 도로를 다 만들면 비용은 15억이 된다. 하지만 A-B, B-C, C-D 도로만 만들면 6억만 쓰면 된다. 이렇게 모든 마을을 연결하면서 비용은 최소인 도로 선택이 바로 MST다. MST(A-B-C-D)에서는 A-B-C-A로 ..