'섬 연결하기' 태그의 글 목록

풀이 과정 프림 알고리즘을 떠올리면 풀이를 쉽게 진행할 수 있다. 섬의 갯수가 1 이상, 100 이하로 주어졌으며 절대로 연결될 수 없는 섬은 주어지지 않는다고 하였으므로 시작지점을 임의로 0번 섬으로 지정하여도 아무런 문제가 없다. 기본적인 풀이의 진행방식은 아래와 같다. Edge의 cost에 대해 오름차순 정렬하는 Priority Queue를 준비한다. 현재까지 방문한 각 섬에 대하여 이하의 과정을 수행한다. 전체 edge에서 현재 선택중인 섬과 연결된 edge를 찾는다. 해당 edge의 다른 한 쪽 끝이 아직까지 방문하지 않은 섬과 연결되어있는지를 확인한다. 방문하지 않은 섬과 연결되어 있는 edge는 다음번에 설치될 다리가 될 가능성이 있으므로 1에서 준비한 Priority Queue에 추가한다...