나그네

3803번: Networking 문제 https://www.acmicpc.net/problem/3803 3803번: Networking You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you a www.acmicpc.net 풀이 여러 테스트 케이스에 대해 MST를 구하는 문제다. 최소 스패닝 트리(MST)는 주..

23034번: 조별과제 멈춰! 문제 https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 풀이 처음에는 X, Y 정점부터 시작하는 최소 스패닝 트리(MST)를 구해줬는데 당연히 시간초과를 받았다. 그래서 생각한 다음 방법은 처음부터 MST를 구해놓은 다음 X와 Y 사이의 가장 큰 가중치를 가지는 간선을 제거해 주는 방법이었다. 처음에는 MST의 간선을 이을 때마다 어느 정점에서 이어졌는지를 기록하고 역추적하는 방식으로 구현했다. 그러나 여..

2887번: 행성 터널 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리(MST)를 구현하기 위해 프림 알고리즘을 사용했다. 각 정점의 3차원 좌표가 주어지고 각 정점 간 실제 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 하지만 모든 정점 사이의 |xA-xB|, |yA-yB|, |zA-zB|를 구하게 되면 N^2의 공간복잡도를 가지게 되어 메모리초과가 난다. 따라..

16398번: 행성 연결 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 풀이 입력 행렬이 각 정점 간 간선의 가중치이므로 i행 j열의 값은 i번째 행성과 j번째 행성 간에 플로우를 설치하는 비용이다. 이를 가지고 최소 스패닝 트리(MST)의 가중치를 구하면 된다. 행성의 수가 최대 1,000개이고 각 가중치의 최댓값이 100,000,000 이므로 최소 스패닝 트리의 가중치의 자료형은 long long 이어야 한다. 코드 #include ..

1922번: 네트워크 연결 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 기본적인 최소 신장 트리(Minimun Spanning Tree, MST)를 사용하는 문제다. 프림 알고리즘으로 구현하는 MST 알고리즘을 사용했다. MST 알고리즘은 아래 글을 보고 공부했다. 아직 유니온 파인드를 모르기 때문에 크루스칼 알고리즘은 보류해놨다. https://4legs-study.tistory.com/112 최소 스패닝 트리 (MST) : 프림 알고리즘 (Prim Algorithm) 최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘..

16940번: BFS 스페셜 문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. BFS의 결과가 가능한지 구하는 문제다. BFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 order 배열을 만들고 먼저 방문해야 하는 정점과 연결된 간선이 앞으로 오도록 간선들을 재정렬 한다. 그리고 BFS를 진행하며 탐색 경로를 구한다. 이 경로가 ..

10423번: 전기가 부족해 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 풀이 이렇게 하면 될까? 했는데 돼서 푼 다음에 이해를 했다. 여러 발전소에서 전력 공급이 가능하기 때문에 프림 알고리즘을 사용하는 최소 스패닝 트리(MST)에서 우선순위 큐에 발전소와 연결된 모든 간선을 넣어줬다. 그리고 MST의 가중치를 구하면 끝! 이를 개념적으로 이해를 해보자면, 결국 최소 스패닝 트리를 만들기 위..

4386번: 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 각 별의 2차원 좌표가 주어지고 별들을 모두 직/간접적으로 최소한의 거리로 이었을 때 거리를 구하는 문제다. 흔한 MST 문제와 달리 약간 생각을 해야한다. 정점 간 가중치가 주어지는 것이 아니기 때문에 각 정점 간 가중치를 직접 구해줘야 한다. 마침 정점의 수 N도 최대 100이므로 모든 정점 간 거리를 구해 간선으로 삼아 MST의 가중치를 구하면 된다. 자료..

16964번: DFS 스페셜 문제 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. DFS의 결과가 가능한지 구하는 문제다. DFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 orde..

1647번: 도시 분할 계획 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 가장 짧은 도로들만 가지고 모든 집이 연결되어 있어야 하므로 집을 정점, 도로를 간선이라고 생각하고 최소 스패닝 트리(MST)를 구하면 된다. 단, 도시를 두 개의 마을로 나눠야 하고 각 마을에는 집이 최소 하나는 있어야 하므로 MST의 간선 중 길이가 가장 긴 간선을 제거해 주면 된다. 코드 #include using ..