정신 차리고 살자

링크 (https://www.acmicpc.net/problem/16398) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 무난한 최소 스패닝 트리 문제이다. MST 문제를 항상 크루스칼 알고리즘으로만 풀었는데 이번엔 프림 알고리즘으로 풀어봤다! 정답이 int 범위보다 클 수 있으므로 long long으로 해주어야 한다. [소스코드] 더보기 2022-03-02 Gold 4 - 그래프 이론 - 최소 스패닝 트리

문제 (https://www.acmicpc.net/problem/14621) 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다. 특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다. 남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다. 만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(B..

문제 (https://www.acmicpc.net/problem/2887) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 입력으로 행성들의 좌표가 들어온다. 이 좌표들로 모든 행성 사이의 거리와 연결 비용을 구한다면 시간 초과가 발생한다. (N ≤ 100,000) 따라서, 행성들의 x, y, z 좌표를 각각 정렬한 후 반복문을 돌며 각 좌표에서 인접한 행성들 간의 비용을 구한다. 예제와 같이 N이 5라면 총 12개의 간선 정보가 생성된다. N이 6이라면 15개이다. 즉 (N-..

문제 (https://www.acmicpc.net/problem/1939) 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이번 스터디 주제인 이분탐색으로 해결하려고 했으나 도저히 모르겠어서 크루스칼로 해결했다 🤯 중량의 최댓값을 구해야 하는 문제이므로 입력을 받은 후 간선의 크기를 기준으로 내림차순 정렬했다. 노드들을 합쳐가면서 매번 마지막 입력으로 들어온 두 섬이 연결되었는지 확인해야 한다. 연결이 되었다면, 연결된 모든 노드들 간의 간선들 중 가..

문제 (https://www.acmicpc.net/problem/4386) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 비용으로 모든 점을 연결하는 MST 알고리즘을 사용한 문제이다. Union-find를 사용하는 크루스칼 알고리즘으로 문제를 해결했다. 이 문제에서는 점 사이의 거리가 주어지지 않고 별의 좌표가 각각 주어지기 때문에 주어진 좌표들로 점 사이의 거리를 구해주었다. (Line 50~61) 위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다. [소스코드] 더보기 2021-12..