[백준_BOJ] 1647. 도시 분할 계획 _ JAVA

문제

 

 

 

 

 

 

 

풀이

 

 

크루스칼 알고리즘을 이용해서 풀이한 문제입니다.

크루스칼 알고리즘을 이용하기 위해 3가지 메서드 union, find, isSame을 만들어주었습니다.

 

이전에 풀이했던 1922. 네트워크 연결 문제처럼 문제풀이를 했다가 메모리 초과가 발생했던 문제입니다.

사실 생각해보면 가장 짧은 비용의 연결선부터 연결하기 때문에 map 배열은 풀이에 필요하지 않습니다.

 

N이 10만까지 가능하기 때문에 2차원 map 배열을 만들면 메모리 초과가 발생합니다.

size 변수를 이용해서 N - 2개의 연결이 만들어질 때까지

가능한 간선들을 계속 연결해주었습니다.

입력이 크다는 점에 주의하면 크루스칼 알고리즘을 이용해 쉽게 풀이할 수 있는 문제입니다.

 

먼저, union 메서드에서는 시작점과 도착점 x, y를 매개변수로 입력받아서

find(x) 와 find(x)가 같지 않다면, 서로 다른 그룹에 속해 있는 것이므로

두 그룹 중에서 작은 값으로 합쳐주었습니다.

크기를 비교하여 합쳐주지 않고 그냥 x나 y로 합쳐주어도 괜찮지만

작은 번호로 합쳐주면 검색 속도를 높여줄 수 있습니다.

 

find 메서드는 자신이 그룹 번호와 같은 경우, 자기 자신을 반환해주었고

자기 자신이 그룹 번호와 같지 않다면, find(parent(x))를 이용하여 그룹에서 

부모 (대표 번호) 가 되는 값을 찾아 반환시켜 주었습니다.

 

마지막으로 union 메서드는 서로 다른 그룹에 속해 있는지를 확인합니다.

이는 이미 같은 그룹에서는 추가적으로 연결해주면 최소값을 제대로 찾지 못하기 때문입니다.

 

 

 

코드

 

 

 

 

 

 

 

 

 

 

 

 

 

출처

 

 

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획