오딩이

https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 크루스칼을 이용해서 해결했습니다. 기존 MST문제들은 무조건 MST를 만들어야해서 편하게 크루스칼을 사용하면 되지만, 이 문제는 MST가 만들어지지 않을 수도 있어서 MST인지 판단해야 하는 로직이 어려웠습니다. 간선을 하나씩 지울 때 마다 노드가 지워지는지 확인하고, 노드가 지워지면 root노드를 초기화해야 합니다. 간선을 지..

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 크루스칼 알고리즘을 사용했습니다. 이미 연결되어있는 노드들을 먼저 연결한 뒤, 우주신들의 좌표대로 크루스칼 알고리즘을 사용하여 MST를 구현했습니다. 크루스칼 알고리즘을 사용하는 것은 어렵지 않았지만, 좌표를 처리할 Pos클래스를 따로 만들어 처리해야 해서 처음 구상이 어려웠습니다. 전체 코드 import java.io.BufferedReader; import ja..