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

문제 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/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 2. 풀이과정 1. 간선의 개수가 노드 수에 비해 현저히 적으므로, kruskal을 선택했다. 2. cost가 적은 간선부터 탐색하기 위해 PriorityQueue를 사용 import java.io.BufferedReader; import java.io.InputS..

1. 문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 2. 풀이 과정 방법 1. bfs 그래프는 MST로 주어지기 때문에, 인접리스트로 입력을 받았다.구현 방식은 매 query마다 bfs탐색을 하며, 가중치가 k이상인 경우만 더 탐색하도록 한다. 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java..

1. 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 2. 풀이과정 MST 알고리즘은 kruskal, prim이 있다. 여기서는 간선의 수가 적으므로 kruskal을 사용했다. 처음에는 전체 edge를 입력으로 받아서 오름차순 정렬 후, 최대 & 최소 MST를 찾았다. 하지만, 이 문제에서는 cost가 0, 1 두 가지로 주어지기 때문에 정렬을 하지 않고 오르막길과 내리막길을 따로 모아서 최대로 만들 수..

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가 최소인 그래프 ..