Hyun's_Devlog

https://www.acmicpc.net/problem/3271

번역기능으로 문제를 봐도 이해되지 않아 헤맸다. chatGPT를 통해 번역과 설명을 보고 나서 이해하여 정답을 받았다..

기본적인 최소 스패닝 문제.

풀이 방법

B마리의 벌들이 F개의 꽃을 최소 스패닝 트리로 구성하여 각 구역을 분담하여 탐색하게 된다. 이때 각 벌들이 분담받은 이동 경로 중 한 번에 가장 많이 이동한 거리의 최솟값을 출력하라는 얘기.

따라서 크루스칼 알고리즘을 컴포넌트가 B개가 될 때까지 진행하고, 이때까지 가장 많이 이동한 거리를 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/23743

기본적인 MST 문제다. 

풀이

두 가지 방법으로 풀었다. 첫 번째로 접근했던 방법은 시간이 조금 빠르지만 코드가 조금 더 길어진다. 

간선의 가중치가 작은 순서로 두 정점 U, V를 연결할 때, 조건을 추가했다. 

두 정점에 워프를 설치하는 비용 > 두 정점을 연결하는 간선 비용 + min( U정점에 워프 설치 비용, V정점에 워프 설치 비용)

두 정점에 탈출구 워프를 설치하는 비용이 더 저렴하다면 두 정점은 연결하지 않는다. 반대로 두 정점에 탈출구 워프 설치 비용이 더 비싸다면 간선을 연결하고 워프를 설치비용이 더 저렴한 쪽이 루트가 되어 연결하면 된다.

이후 각 컴포넌트의 루트 정점에 워프설치 비용을 더해주면 가장 작은( 간선 + 워프 설치 ) 비용이 나오는데, 마지막으로 한번 더 모든 정점에 워프 설치비용과 비교하여 더 작은 쪽을 출력하였다.

두 번째 방법은 탈출구를 0번 정점으로 취급하여 간선정보를 정렬한 뒤 MST를 수행하면 간단하게 구할 수 있다.

정답 코드-1

정답 코드 - 2

https://www.acmicpc.net/problem/1833

MST 알고리즘의 기본문제다. 크루스칼 알고리즘을 통해 해결했다.

유니온 함수의 구현에서 사소한 실수를 해서 WA를 받아 당황했지만 실수를 금방 발견했다.

풀이

주어지는 간선은 양방향 간선이므로 u (0 ..< N), v (u+1 ..< N) 탐색을 통해 중복되는 정보는 배제하고 탐색하였다.

간선이 음수면 이미 연결된 고속도로 이므로 절댓값을 totalCost에 더한 뒤, 두 정점을 연결한다. 주의할 점은 이미 부모가 같은 정점끼리의 간선이 음수로 주어질 수도 있으므로 있으므로 예외처리를 해주어야 한다.

나머지의 경우는 edges 배열에 담아낸 뒤 비용이 적은 간선부터 유니온 함수를 수행한다. 이때 연결된 간선은 배열에 따로 정보를 담아주었다가 출력해 주면 된다.

정답 코드