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