백준 [1647] kotlin

문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 문제의 조건을 보면, 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 두 가지 조건이 있습니다. 두번째 조건을 보면, 최소 신장 트리를 찾아내야 하는 문제입니다. 그리고 가중치의 경우에는 첫번째 조건을 통해 알 수 있습니다. 곧 두 별 사이의 거리가 가중치입니다. 최소 신장 트리를 구하는 방법..

• format_list_bulleted 그래프 이론
• · 2023. 7. 21.
• textsms

백준 [1647] kotlin

[문제] https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net [풀이] 최소 신장 트리를 만들어 주고, 최소 신장 트리의 모든 가중치의 합에서 최소 신장 트리에서 가장 큰 가중치를 빼면 답이다. [코드] import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStre..

• format_list_bulleted 그래프 이론
• · 2023. 2. 1.
• textsms

백준 [1976] kotlin

[문제] https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [풀이] 문제 푸는 과정은 2가지로 크게 나뉜다. 1. union-find를 이용하여, 경로 정보를 입력받아 spanning tree를 만든다. 2. spanning tree의 부모를 체크하여, 여행 경로가 같은 경로상에 존재하는지 확인한다. 입력받은 도시의 길을 기반으로 spanning tree를 만들기 위해 union-find를 사용했다. spanning tree를 만들었으면 여행 경..

• format_list_bulleted 그래프 이론
• · 2023. 1. 13.
• textsms