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

문제 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/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. 그래프 그래프는 정점과 간선으로 구성되어 있다. 그래프는 방향성이 없는 '무방향 그래프'와 방향성이 있는 '방향그래프'로 나눠볼 수 있다. '각각 정점에서 다른 모든 정점을 연결한 그래프'를 '완전 그래프'라고 하며 아래 두 그래프가 이에 해당한다. 2. 그래프 구현방법 1) 인접 행렬(adjacent matrix) 기반 그래프 2차원 배열을 이용한다. 2) 인접 리스트(adjacent list) 기반 그래프 연결 리스트를 활용하여 그래프를 표현한다. 3. 그래프의 탐색 1. 깊이 우선 탐색 (DFS : Depth First Search) 자신과 연결된 노드들 중 내용이 전달 안 된 하나를 먼저 선택해서 그 사람과 연결된 노드들에게 내용을 다 전달하면, 다음 하나를 또 선택한다. 백트래킹이라고도 하..