My life story

1. 문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 문제 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우� www.acmicpc.net 2. 문제 개요 주인공과 우주신들을 모두 연결해야 한다. 간접적으로 연결하여도 괜찮다. 이미 연결된 통로가 주어지고, 모두 연결하기 위한 통로길이의 합의 최솟값을 구해보자. 3. 문제 힌트 Kruskal 알고리즘을 사용해야한다. (1) 그런데, 이미 연결된 통로가 있다. 이런 경우에는 어떻게 전처리를 해야 할까? (2) 경로는 어떻게 구할까? 위의 두 가지 생각해야 할 점이 있다. ..

1. 문제 링크 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. � www.acmicpc.net 2. 문제 개요 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 두 행성을 x, y, z 좌표로 나타내고, 터널로 연결할 때 드는 비용은 min(|x2-x1|, |y2-y1|, |z2-z1|)로 정의한다. 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하자..

1. 문제 링크 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 2. 문제 개요 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을을 2개로 쪼개고, 각 마을의 집들은 다 연결되어있어야 한다. 길의 최소비용을 구해보자. 3. 문제 힌트 (1) 마을1개에서 모든 집들을 가장적은 비..