공부하자

https://www.acmicpc.net/problem/6497난이도는 그렇게 높진 않았는데, 문제 자체에 함정이 몇 개 정도 있는 문제였던 것 같다. 질문 게시판에도 여럿 문제의 입력과 출력 조건에 대해 까다로워 하는 모습이 보였다. 다음은 질문게시판에 있는 한 글을 발췌한 것이다.  https://www.acmicpc.net/board/view/1453601. 제시된 예제는 테스트 케이스가 하나입니다만, 0 0이 등장하기 전에 테스트 케이스가 여러 개가 있을 수 있으므로, 각 테스트 케이스에 대한 정답을 차례차례 저장해두어야 합니다.2. 모든 정답은 '0 0'이 입력된 이후에 순차적으로 출력해야 합니다. (댓글 보고 추가: 하나씩 출력하는 것도 가능하다면 이 항목은 무시하셔도 됩니다.)=> 수정 :..

https://www.acmicpc.net/problem/1647최소 신장 트리, MST를 다루는 기본적인 문제이다.인접리스트 형태로 주어지는 그래프에 대해 MST를 생성하면 되는 문제인데, 한가지 조건이 더 붙었다. 해당 MST를 두 집합으로 나누어서 가중치의 합이 가장 적은 MST 형태를 만들어 내면 되는 것이다. 당연히 그래프를 둘로 나누고 할 필요없이 결론적으로는 MST를 생성하여 구해진 가중치의 합에서 가장 가중치가 큰 간선을 빼주면 된다.이렇게 방향성을 잡고 풀면 되는데 MST 구현에는 보통 두가지 접근 방식이 있다. 하나는 프림 알고리즘 (Prim's Algorithm) 이고, 다른 하나는 크루스칼 알고리즘 (Kruskal's Algorithm) 이다. 전자는 우선순위 큐와 방문여부를 체크하..