백준 17472 파이썬1 17472. 다리 만들기 2 (Python) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 다음과 같은 과정을 통해서 문제를 해결한다. 먼저 각 섬에 번호를 붙여주는 작업을 한다. 각 섬에서 위, 아래, 왼쪽, 오른쪽으로 탐색하여 다리를 만들어본다. 섬에서 다른 섬으로 가는 다리 중에서 가장 짧은 거리를 갖고 있는 다리의 정보를 저장한다. 저장한 다리를 다리의 길이를 기준으로 오름차순 정렬한다. 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구성한다. 사용된 다리의 길이들을 합한 값을 출력한다. 코드 import sys imp.. 2022. 4. 30. 이전 1 다음
