개발하는 고라니

14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net [크루스칼] 최소 스패닝 트리를 만드는 문제인데 약간 문제에 낚였다고 해야하나.. "만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다." 라는 문장 때문에 항상 부모가 1번 도시와 연결되어있어야 하는 줄 알고 풀었더니 시간이 2s가 넘게 걸렸다. 아무리 생각해도 이건 아닌 것 같아 일반적인 크루스칼 알고리즘 처럼 풀었더니 정답으로 인정되었다. 코드로 보는 것이 더 이해가 쉬울 듯 하다. int sum = 0;..

10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net [크루스칼 알고리즘] 보통 MST하면 모든 정점이 하나의 덩어리로 연결되는 것을 생각할 수 있는데, 이 문제의 경우 발전소의 개수(k)개의 덩어리로 나뉘어 모든 정점이 연결되었을 때의 합을 출력하는 문제이다. 나는 유니온-파인드 부분을 수정했다. 보통 유니온-파인드는 두 정점 a, b를 받아 더 작은 번호를 부모 노드로 삼는 것이 일반적인데, Set에 발전소의 번호를 넣어두고 1) 두 정점 모두 발전소에 연결되어있지 않다..

코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr [Kruskal 알고리즘] 입력으로 들어오는 land[ ][ ]의 각 원소에 인덱스를 부여했다. 이차원 배열에서 인덱스를 부여하는 방법은 (i * N) + j 이다. 이렇게 하면 0부터 N-1 * N-1까지 원소에 대해 인덱스를 부여할 수 있다. 이는 곧 정점을 정의할 수 있다는 것이므로 크루스칼 알고리즘을 수행하기에 더욱 수월해진다. 우선 이중 for문을 돌며 land의 각 원소에 대해 상..

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net [BFS * m회 + Kruskal (=Union-Find, Sort)] 어느정도 발상의 전환이 필요한 문제라고 생각된다. 'S'에서부터 'K'를 찾아가는 것이 아닌 각각의 'K'에서 또다른 'K'나 'S'를 찾아가는 방법으로 풀어보았다. 그러므로 m개의 'K'가 주어지면, 각각의 'K'의 위치에서 BFS를 수행하며 다른 'K'나 'S'를 만날 때 간선의 정보를 만들어 List에 담아주었다. 이 때 크루스칼 알고리즘을 수행하려면 출..

16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net [Kruskal, 최소 스패닝 트리] 문제에서 주어지는 인접 행렬의 정보를 받아 시작 정점(h), 도착 정점(tg) 그리고 비용(c)를 List에 담아 오름차순 정렬 후 크루스칼 알고리즘을 수행한다. 이 때 주의할 점은 비용은 최대 100,000,000이므로 비용을 더할 때 int가 아닌 long에 담아주도록 한다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.In..

4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net # 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. # 입력 첫째 줄에 ..

2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net # 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해..

크루스칼(Kruskal) 알고리즘 이 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 사이클(Cycle)을 만들지 않는 범위에서 최소 비용 간선(Edge)을 하나씩 더해가며 최소 신장 트리(Minimum Spanning Tree, MST)를 만든다. 실제로 여러 도시가 있을 때 각 도시를 도로로 연결하는데 최소 비용을 들여 연결할 때 사용될 수 있는 알고리즘이다. n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요하므로, 처음에 간선이 없는 상태에서 시작하여 n-1개의 간선을 더하는 것이다. 크루스칼 알고리즘은 프림 알고리즘 처럼 하나의 트리를 키워나가는 방식이 아니고, 임의의 시점에 최소 비용의 간선을 더하므로 여러 개의 트리가 산재하게 된다. 크루스칼은 시작점을 정..