[ LeetCode ] 827. Making A Large Island

문제 링크

문제 링크

문제 설명

n*n grid 에서 면적이 가장 큰 섬을 구하는 문제입니다. ( 육지는 1 / 바다는 0으로 표현 ) 여기서 특이점은, 0중 하나를 1로 바꿀수 있다는 점입니다.

사용한 알고리즘

* union-find
heuristic

풀이 설명

1. union find 로 각 섬들을 대표하는 부모 cell 을 뽑아냄 ( 이 때 각 부모는 자신의 전체 자식들의 x,y 좌표를 벡터로 들고 있음 )
2. 각 섬의 모든 멤버를 순회하면서 주변의 인접 바다에 마킹
3. 바다 중 여러 섬에 인접한 ( 위에서 여러 섬에 의해 마킹된 ) cell 이 있을 경우, 이 때 결과 후보에 인접한 섬들의 면적 합 + 1 을 추가함
4. 각 섬들의 면적 + 1 을 을 결과 후보에 추가함
5. 결과 후보들을 소팅하여 가장 큰 값을 뽑아냄
6. 가장 큰 값이 nn 보다 크면 ( 모든 cell 이 육지인 경우 ) nn 을 반환, 아니면 그냥 반환

소스 코드

union-find 가 궁금하다면

https://hvho.github.io/2021-02-21/baekjoon-4195