크루스칼10

• 

  [백준/BOJ] 1185번: 유럽여행 문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 해설 N-1개의 길만을 남겨야 한다. 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 위 3 문장은 문제에서 가장 핵심이 된다 생각한 것들이다. 우선 1, 2번을 보면 최소 신장 트리를 구해야 한다는 것을 알 수 있다. 이때, 문제에서는 각 나라에 .. PS(Problem Solving)/BOJ 2022. 8. 31.

• 

  [백준/BOJ] 17472번: 다리 만들기2 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 해설 문제를 읽어보면, 크게 3가지 과정을 나눠야하는 것을 알 수 있다. 섬을 구분짓는다. 섬을 잇는 다리를 놓는다. 모든 섬이 연결되었는지 확인 및 다리의 총 길이를 구한다. 단계별로 나가보자. 우선 섬을 구분지어야 한다. 나는 우선 섬으로 표시된 1을 전부 -1로 저장해주었다. 이후 BFS를 사용하여 섬에 번호(1, 2, 3, 4, . . .)를 붙여주었다. repe.. PS(Problem Solving)/BOJ 2022. 8. 25.

• 

  [백준/BOJ] 16202번: MST 게임 문제 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 해설 제목에서부터 알 수 있듯이 MST를 응용하는 문제이다. 최소 신장 트리를 구하기 위해 크루스칼 알고리즘을 사용하였다. 문제에서 가장 중요한 문장은 아래 문장이다. 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다. 결론적으로는 한 턴이 끝날 때마다 가장 작은 간선을 제거하여 k만큼 .. PS(Problem Solving)/BOJ 2022. 8. 12.

• [백준/BOJ] 1368번: 물대기 문제 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 해설 논에 물을 대는 방법은 두 가지가 있다. 직접 논에 우물을 판다. 이미 물을 대고 있는 다른 논으로부터 물을 끌어온다. 즉, 논에 우물을 파는 비용과 논 사이를 연결하는 하는 비용을 비교해야 하는 문제이다. 어렵게 생각할 것 없이, 우물을 파는 비용을 담는 정보도 간선에 추가해주면 된다. 즉, 노드를 한개 더 만든다 생각하면 된다. 예를 들어, 문제의 예시.. PS(Problem Solving)/BOJ 2022. 8. 1.

• [백준/BOJ] 1774번: 우주신과의 교감 문제 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 알고리즘을 사용하는 문제이다. 따로 어떤 노드부터 시작해라라는 말이 없으므로 크루스칼 알고리즘을 사용하였다. 황선자씨는 이미 교감하고 있는 우주신들이 있다. 따라서 우선적으로 이미 교감하고 있는 우주신들을 union을 통해 합집합 연산을 해준다. 이후 아직 연결되지 않은 우주신들과의 거리를 구하여 우선순위 큐에 시작점,.. PS(Problem Solving)/BOJ 2022. 7. 30.

• [백준/BOJ] 6497번: 전력난 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 해설 문제를 보면 MST 알고리즘을 사용해야 한다는 것을 알아야 한다. 최소 신장 트리를 구해 총 비용에서 최소 비용을 빼어 절약할 수 있는 최대 액수를 구한다. 어떠한 정점에서 시작해야 된다와 같은 조건이 없으므로, 크루스칼 알고리즘을 사용하였다. 이 문제에서 주의할 점은 입력에 있다. 처음 제출했을 때, 런타임 에러가 나 무엇이 문제인지 고민하다 질문 검색에 들어가 나랑 같은 케이스인 사람들이 있는.. PS(Problem Solving)/BOJ 2022. 7. 28.

• [백준/BOJ] 21924번: 도시 건설 문제 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 해설 최소 신장 트리(MST)에 대해 알고 있다면, 굉장히 쉬운 문제이다. 모든 간선의 비용을 합한 값에서 최소 신장 트리를 구해 그만큼의 비용을 빼주면 된다. 나는 크루스칼 알고리즘을 이용하였다. 주의할 점으로는 입력 범위가 크므로 int형을 사용한다면 틀리게 된다. .. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 4386번: 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 해설 처음 입력으로 별의 개수와 별의 좌표를 입력받는다. 이번 문제에서는 기본적인 수학의 개념도 필요하다. 두 점 사이의 거리를 구해야하기 때문이다. 두 점 사이의 거리를 구하는 공식은 다음과 같다. √(x2-x1)2 + (y2-y1)2 두 별 사이의 거리를 구하는 방법을 알았다면, 별 거 없다는 것을 다들 알 수 있다. 이제 크루스칼 알고리즘을 이용하여 최소 비용을 구하면 된다. 이 때 소수.. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 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 해설 1. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 2. 마을에는 집이 하나 이상 있어야 한다. 3. 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 4. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 위는 문제에서 .. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 1197번: 최소 스패닝 트리 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 해설 최소 신장 트리의 기본적인 문제이다. 크루스칼 알고리즘과 프림 알고리즘으로 해결이 가능한데, 나는 우선 크루스칼 알 고리즘을 이용하여 해결하였다. 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택해 나가는 알고리즘이다. 자세한 설명은 아래를 참고하면 된다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고.. PS(Problem Solving)/BOJ 2022. 7. 22.