그래프

아이디어 책에 있는 최소 신장 트리 코드를 학습한 뒤 풀었더니 너무 손쉽게 풀렸다. 주의 해야 할 점은 가중치를 기준으로 오름차순 정렬 해줘야 하기 때문에 (가중치, 노드1,노드2) 이 순서대로 값을 저장해줘야 한다는 것 코드 코드를 이해했지만 외운 느낌이라 나중에 한 번 더 풀어봐야 할 것 같다.

아이디어 "모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다" 이 부분을 보고 최소신장트리 문제라는 것을 알 수 있었다. 이전 최소 스패닝 트리 문제와 동일했기에 쉽게 풀었다. 코드

아이디어 바로 직전에 풀었던 문제 2개가 최소신장트리 문제여서 이 문제도 최소신장트리 문제인줄 알았는데, 문제를 읽어보니 가중치값이 없었다. 따라서, "상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수"는 그저 간선의 개수 - 1 이라는 것을 알 수 있었다. 다만, 이 풀이가 맞는지는 잘 모르겠다... 코드

시간초과 발생 -> heapq 사용4% 시간초과........도움 https://www.acmicpc.net/board/view/64342heapq에 삽입할 때 가중치값이 우선순위가 되어야 한다.=> heapq.heappush(heap,가중치,노드값) 이렇게