네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 과정 MST문제로 풀이 방법은 Prim과 Kruskal 두 가지가 있는데, 간선의 개수가 많으므로 Prim을 선택하여 풀었다. 하지만, 아래의 메서드를 보면 거리 계산하는 함수에서 Math.pow를 쓰지 않고 곱셈을 쓰면 기본이 int형으로 계산되기 때문에 값이 정확히 측정되지 않아 통과하지 못한다. public static double getDistance(..

1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이과정 MST 문제로 Kruskal이나 Prim으로 접근할 수 있다. 노드 수가 1000개, 간선 수가 최대 100,000로 N(N-1)보다 10배 적은 수이다. 따라서 여기서는 kruskal을 활용해서 풀었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { s..

1. 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 2. 풀이 과정 MST 문제이고, kruskal와 prim이 떠올랐다. 두 가지 알고리즘을 각각 사용해서 두 번 풀어봤는데, 간선의 개수가 많기 때문에 kruskal보다 prim이 훨씬 빨랐다. 1. Kruskal 더보기 import java.io.*; import java.util.*; public class Main { static int N, p[]; public static Pr..

1. 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 풀이 과정 필요한 데이터를 만들어서 푸는 MST문제이다. MST 문제 해결 방법은 Kruskal과 Prim이 있는데 정점 기준으로 데이터를 기록했기 때문에, Prim을 사용했다. 1. 섬마다 번호 붙이기 2. 섬과 섬까지 거리 구하기 가로, 세로 각각 for문 돌면서 최솟값 갱신시켜나감 3. MST 구하기 *cycle없이 다 이어진, cost가 최소인 그래프 ..