MST
-
[백준]16202: MST 게임 - JAVA문제풀이/백준 2021. 9. 8. 14:41
[백준]16202: MST 게임 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 🪑 문제에서도 알 수 있듯이 MST문제였다. MST라는 것을 알려주지 않았 더라도 전형적인 MST문제이기 때문에 어렵지 않았을 것으로 예상되는 문제였다! 📝 문제를 정리해 보자! N개의 정점과 M개의 양방향 간선으로 이뤄진 그래프가 있다. K턴동안 진행되며 첫 턴에 MST를 구한다. 각 턴이 종료된 후 MST중에서 가중치가 가장 작은 간선을 제거한다. 나머지 간선..
-
[백준]1944: 복제 로봇 - JAVA문제풀이/백준 2021. 8. 14. 19:26
[백준]1944: 복제 로봇 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 풀이 🪑 이 문제는 어떻게 풀어야 하는지 도저히 모르겠었던 문제였다! 로봇이 움직이는 횟수의 합을 최소로 하기 위해서 BFS를 떠올렸지만, K를 만날 때마다 복제가 된다는 조건 때문에 방문 체크를 어떻게 처리해야 할지 걱정되었던 문제였다. 그래서 문제의 '알고리즘 분류'에서 MST라는 힌트를 얻었다. 막상 MST라는걸 알고 나니 되게 쉽게 느껴졌던 문제였다. 📝 문제를 정리해 보자! 모든 열쇠를 찾으면서..
-
[백준]13418: 학교 탐방하기 - JAVA문제풀이/백준 2021. 8. 12. 17:47
[백준]13418: 학교 탐방하기 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 풀이 🪑 MST를 활용한 문제였다. 최소 간선 트리를 구하는 MST를 활용하여 최대 간선 트리도 구해주면 된다. 📝 문제를 정리해 보자! 출발 건물은 0이며 항상 출발 건물에서 모든 건물로 갈 수 있다. 오르막길을 K번 오르면 피로도는 K^2이다. 최악의 피로도, 최소의 피로도를 가지는 경로의 피로도 차이를 구한다. 🔧 문제를 풀어 보자! 간선의 정보를 입력 받을 때 양 방향으로 정보를 입력 받는다. ..
-
[백준]17472: 다리 만들기 2 - JAVA문제풀이/백준 2021. 8. 6. 15:11
[백준]17472: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 🪑 구현 + BFS + DFS + MST + 완탐의 아이디어가 들어간 문제였다. 이 중에서 가장 중요한 부분은 MST이다. 📝 문제의 조건을 정리해 보자. 다리의 방향이 중간에 바뀔 수 없으며 길이는 2 이상이어야 한다. 섬을 모두 연결하는 다리의 최소 길이를 구한다. 다리는 교차될 수 있으며 교차되는 경우 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 모든 섬을 연결하는 것이 불가능 하면 -1을 ..
-
[백준]20010: 악덕 영주 혜유 - JAVA문제풀이/백준 2021. 7. 7. 17:08
[백준]20010: 악덕 영주 혜유 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 풀이 🪑 MST를 구하는 활용문제이다. 문제의 조건들을 정리해보자. 마을간 교역로는 양방향이다. 모든 마을은 연결되어있다. 구하는 값은 MST 비용과 MST 내에서 가장 먼 노드간의 거리이다. 🔧 이제 문제 풀이 과정을 생각해 보자. 마을 간 교역로 정보를 입력 받은 후 MST를 구한다. MST를 저장해 둔 다음 MST를 내에서 DFS로 가장 먼 노드간의 거리를 구한다. 가장 먼 노드간의 거리를 구하기 위해선 먼저, 한 정점에..
-
[백준]6479: 전력난 - JAVA문제풀이/백준 2021. 5. 31. 11:36
[백준]6479: 전력난 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 방향성이 없는 n개의 간선으로 연결된 m개의 노드 중에서 MST를 비용을 찾는 문제이다. MST를 찾아야 하는것은 맞지만 결과로 반환하는 값은 MST값이 아니다. 문제를 읽어보면 결국 최소 비용을 가질 수 있는 불이 켜진 길로만 이동할때 절약할 수 있는 최대 비용을 찾는것이다. 즉, 전체 비용에서 최소비용을 뺀 값이 우리가 구하려고 하는 값이 된다. 그러므로 prim이나 kru..
-
[백준]4386: 별자리 만들기 - JAVA문제풀이/백준 2021. 4. 26. 19:04
[백준]4386: 별자리 만들기 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 별들의 좌표를 간선으로 이었을때 최소인 비용을 찾는 문제로 MST알고리즘을 사용하여 풀면 된다. 별을 입력받을때 해당 별의 번호와 좌표를 저장해 주었다. 이 문제에서는 별들이 연결된 간선의 정보가 없으므로 모든 별들 사이의 거리를 직접 구하여 간선list에 저장해 주었다. 그다음 MST알고리즘인 prim, kruskal알고리즘을 사용하여 각각의 MST를 구해주면 된다. 코드 ..
-
[백준]1647: 도시 분할 계획 - JAVA문제풀이/백준 2021. 3. 1. 18:34
[백준]1647: 도시 분할 계획 www.acmicpc.net/problem/16471647번: 도시 분할 계획첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집www.acmicpc.net풀이집이 모두 연결되어 있는 상태에서 연결된 집을 두개의 마을로 나누는 문제이다. MST알고리즘을 사용하여 풀면 된다.MST알고리즘은 최소 간선을 선택해서 모든 노드를 연결한 경로를 찾는 알고리즘이다. 이 문제의 어려웠던 점은 하나로 연결된 집을 간선의 비용을 최소로 갖는 두 개의 마을로 나누는 부분이다. 처음에는 어떻게 해야 하나 감이 안잡혔지만..