[leetcode] 827. Making A Large Island

문제 : https://leetcode.com/problems/making-a-large-island/

---

n x n 크기의 0과 1로 이루어진 grid 배열이 입력으로 주어질 때, 1로 이루어진 섬의 최대 크기를 구하여라.

이 때, 최대 한 번 0을 1로 바꿀 수 있다.

---

dfs를 한 번 돌리면서 연결된 1들을 하나의 섬으로 보고 섬의 번호와 해당 섬의 크기를 map에 저장한다.

grid 배열을 한 번 더 탐색하면서 탐색하는 셸이 0인 경우 해당 셸의 상하좌우에 있는 섬의 번호들을 가져온다.

상하좌우에 있는 섬들의 합 + 1 (탐색중인 0 셸이 1로 바뀌면서 증가된 섬의크기)들이 하나의 0을 1로 바꿨을 때 구할 수 있는 섬의 크기이다.

구할 수 있는 섬들의 크기들 중 최대값이 정답이 된다.

 

시간/공간 복잡도는 O(n^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/827.%20Making%20A%20Large%20Island.cpp