너구리의 코딩 블로그

문제 풀이 크루스칼 알고리즘을 이용해서 풀이한 문제입니다. 크루스칼 알고리즘을 이용하기 위해 3가지 메서드 union, find, isSame을 만들어주었습니다. 이전에 풀이했던 1922. 네트워크 연결 문제처럼 문제풀이를 했다가 메모리 초과가 발생했던 문제입니다. 사실 생각해보면 가장 짧은 비용의 연결선부터 연결하기 때문에 map 배열은 풀이에 필요하지 않습니다. N이 10만까지 가능하기 때문에 2차원 map 배열을 만들면 메모리 초과가 발생합니다. size 변수를 이용해서 N - 2개의 연결이 만들어질 때까지 가능한 간선들을 계속 연결해주었습니다. 입력이 크다는 점에 주의하면 크루스칼 알고리즘을 이용해 쉽게 풀이할 수 있는 문제입니다. 먼저, union 메서드에서는 시작점과 도착점 x, y를 매개변수..

문제 풀이 Union-Find를 이용하여 풀이해야 하는 문제입니다. 0일 때 union 연산을 수행하고 1일 때 같은 집합에 있는지를 비교하기 때문에 flag 변수를 만들어서 분류해주었습니다. 문제에서 여러 번 isSame( ) 연산을 수행하기 때문에 StringBuilder( ) 를 이용해서 한 번만 출력할 수 있도록 해주었습니다. 추가적으로, union( ) 연산에서 연산의 수행속도를 높여주기 위해 x y 중 큰 수를 부모로 바꾸어주도록 하였습니다. 코드 출처 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연..