최소 스패닝2 백준 17472 다리 만들기2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 핵심 파악하기. 1. 모든 섬을 최소 길이의 다리로 모두 이어줄 때 다리 길이의 합을 출력하는 문제입니다. 2. 섬과 섬을 다리로 이어줄 때 길이는 2이상이어야 하며, 다리가 교차하더라도 교차 구간의 길이가 1이 되는 것이 아닌 각각의 다리의 길이를 포함하여야 합니다. 풀이. 1. 각각의 섬을 다음과 번호를 붙여 구분해 줄 것입니다. 2. 각각의 섬이 다른 섬으로 이동할 때 최소 거리를 완전 탐색 + bfs를 이용하여 구해줍니다. 3. .. 2022. 5. 28. 백준 4386 별자리 만들기 js 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이. 별자리들의 좌표가 주어졌을 때 최소 비용으로 모든 별자리를 잇는 최소 스패닝 트리 문제입니다. union-find개념과 더불어 크루스칼 알고리즘을 공부하면 쉽게 풀 수 있는 문제입니다. union-find의 개념은 여기서 쉽게 배울 수 있습니다. 크루스칼 알고리즘은 여기서 쉽게 배울 수 있습니다. 1. 모든 별자리를 입력받고 모든 경우의 별자리 사이의 거리를 queue 변수에 담아줍니다. 2. 비용을 기준하여 오름차순 정렬해줍니다. 3. 무한 루프가 생기지.. 2022. 3. 9. 이전 1 다음
