MST
-
[백준 4386 - JAVA] 별자리 만들기Algorithm 2020. 11. 12. 17:52
4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 기본적인 MST (최소스패닝트리) 문제! 나는 입력을 잘 못 받아두고 왜 안되냐고 고통받다가 나중에 발견했다 :( 프림이나 크루스칼 둘 중에 한가지를 사용해서 풀 수 있는데, 나는 프림을 사용해서 풀었다. 크루스칼은 union, findSet을 구현하기가 너무 귀찮았다 =(:з」∠)_ 풀이 방법 입력받은 좌표를 이용해 다른 별과의 거리를 구한다. 첫번째 별부터 시작! 다른 별들의 번호와 첫번째별과의 거리를 Edge 객체로 만들어 PQ에 넣는다. 방문한 별의 개수(..
-
[백준 2887 - JAVA] 행성터널Algorithm 2020. 11. 9. 18:09
2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다! 간선을 찾고 MST로 연결하는 것은 쉽지만, 행성의 개수가 100,000개로 시간초과 혹은 메모리 초과가 발생하는 문제다. 나같은 경우에도 메모리 초과를 3번 겪고난 후 다른 블로그를 참고하여 문제를 해결했다. 풀이 방법 각 행성의 Index와 x, y, z를 저장하고 Union-Find에서 사용할 배열을 초기화한다. 행성들의 거리를 계산하여 간선으로 PQ에 삽입한다. ..