MST (4) 썸네일형 리스트형 [Baekjoon] 백준 21924번: 도시 건설 (JAVA) 문제 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 [ 문제 풀이 ] 모든 건물을 최소한의 비용으로 연결하는 문제이므로 크루스칼 알고리즘으로 풀면 됩니다. 크루스칼 알고리즘에 대한 자세한 설명은 아래 포스트를 참고해주세요 :) [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘.. [SWEA] 4006. 고속도로 건설 2 (with JAVA) 문제 4006 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [ 접근 과정 ] 문제에서 이미 '최소 비용' 이라는 말이 나와있어서, 가중치를 계산하는 문제라는 것을 알 수 있었습니다. '최소 비용으로 모든 도시 간을 이동할 수 있게' 라는 부분에서 크루스칼 알고리즘을 사용하면 좋을 것 같다는 생각을 했습니다. 여기서의 간선은 도로이기 때문에 무향 그래프로 이해했고, 도로를 기준으로 최소 비용의 도로들을 선택해서 모든 도시를 이을 수 있어야 하기 때문에, 사이클이 없어야 하는 크루스칼 알고리즘으로 해결했습니다. 크루스칼 알고리즘을 공부하기에 앞서 서로소 집합을 트리로 표현하는 부분에 대해 먼저 알고 있어야 합니.. [SWEA] 1251. 하나로 (with JAVA) 문제 1251 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [ 접근 과정 ] 문제를 보면, 섬들 간의 거리를 간선의 가중치로 볼 수 있습니다. 가중치 하면 기본적으로 떠오르는 알고리즘이 다익스트라였기에 다익스트라 알고리즘을 이용해서 풀었습니다. 다만, 이전까지 다익스트라 알고리즘 기본 문제들을 풀었을 때는 간선들의 가중치가 주어졌었지만, 이번 문제는 가중치도 직접 구해야 했습니다. [ 고민했던 부분 ] 1. 각 섬들의 위치를 어떻게 저장할 것인가? 각 섬들의 위치를 저장할 때 ArrayList() 를 써야하나 고민했지만, 문제에 나온 x, y 의 범위를 고려했을 때 2차원 배열로 해도 충분할 것이라 생각해서.. [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘에서 이용되는 서로소 집합과 연산에 대해 정리해보겠습니다. 일단, 서로소는 공통으로 포함하는 원소가 없는 두 집합의 관계입니다. 아래와 같이 A, B 집합이 있을 때, 두 집합에서 공통되는 원소가 없다면 'A와 B는 서로소이다' 라고 말할 수 있습니다. 서로소 집합에서 연산은 크게 3가지가 있습니다. [ Make-Set 연산 ] >> 자기 자신인 집합을 하나 만듭니다. 즉, 자기자신이 대표원소가 됩니다. 여기서 대표원소는 부모노드가 자기자신일 때입니다. 예를 들어, 0부터 5까지 Make-Set 연산을 하게 되면 아래 그림과 같습니다. Make-Set(0) ~ Make-Set(5) [ Union-Set 연산 ] .. 이전 1 다음
