C++ DFS로 해결하는 '가장 큰 섬 만들기' 알고리즘

문제 소개

0과 1로 이루어진 2차원 이진 그리드가 주어집니다. 우리는 최대 하나의 0을 1로 변경할 수 있으며, 변경 후 만들 수 있는 가장 큰 섬의 크기를 구해야 합니다. 여기서 섬이란 상하좌우(4방향)로 연결된 1들의 그룹을 의미합니다.

예를 들어 입력이 [[1, 0], [0, 1]]이라면 출력은 3입니다. 하나의 0을 1로 바꾸면 두 개의 1이 서로 연결되어 넓이가 3인 섬을 얻을 수 있기 때문입니다.

해결 전략

이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

섬 라벨링: DFS로 각 섬을 탐색하면서 섬마다 고유한 인덱스(2부터 시작)를 부여하고, 각 섬의 넓이를 배열에 저장합니다.
연결 시뮬레이션: 모든 0인 칸을 순회하면서, 해당 칸을 1로 바꿨을 때 인접하게 되는 서로 다른 섬들의 넓이를 합산합니다.
중복 방지: 집합(set)을 사용해 인접한 섬의 인덱스를 관리하므로, 같은 섬이 여러 번 더해지는 것을 막을 수 있습니다.
최댓값 갱신: 각 경우마다 (인접 섬들의 넓이 합 + 1)을 계산해 기존 최댓값과 비교한 뒤 답을 갱신합니다.

알고리즘 단계

크기가 4×2인 방향 배열 dir을 정의합니다: dir := {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
idx, i, j와 그리드를 매개변수로 받는 dfs() 함수를 정의합니다.
(i, j)가 그리드 범위를 벗어나거나 grid[i][j]가 1이 아니면 0을 반환합니다.
ret := 1로 초기화하고, grid[i][j] := idx로 현재 섬에 인덱스를 표시합니다.
k를 0부터 3까지 증가시키며 네 방향 좌표 (ni, nj)를 계산하고, ret에 dfs(grid, ni, nj, idx)의 결과를 누적한 뒤 ret을 반환합니다.

메인 함수 처리 과정

ret := 0, idx := 2로 초기화하고, 크기가 2인 area 배열을 선언합니다.
n := 그리드의 행 개수, m := 그리드의 열 개수로 설정합니다.
모든 칸을 순회하며 grid[i][j]가 1이면 dfs를 호출한 결과를 area에 추가하고, ret을 갱신한 후 idx를 1 증가시킵니다.
다시 모든 칸을 순회하며 grid[i][j]가 0인 경우, 상하좌우에 인접한 섬의 인덱스를 집합 idxs에 수집합니다.
temp := 1로 초기화한 뒤 idxs에 포함된 각 섬의 넓이를 temp에 더하고, ret을 갱신합니다.
모든 순회가 끝나면 ret을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    int dfs(vector<vector<int>>& grid, int i, int j, int idx){
        if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()
        || grid[i][j] != 1) return 0;
        int ret = 1;
        grid[i][j] = idx;
        for(int k = 0; k < 4; k++){
            int ni = dir[k][0] + i;
            int nj = dir[k][1] + j;
            ret += dfs(grid, ni, nj, idx);
        }
        return ret;
    }
    int largestIsland(vector<vector<int>>& grid) {
        int ret = 0;
        int idx = 2;
        vector<int> area(2);
        int n = grid.size();
        int m = grid[0].size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    area.push_back(dfs(grid, i, j, idx));
                    ret = max(ret, area.back());
                    idx++;
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 0){
                    set<int> idxs;
                    for(int k = 0; k < 4; k++){
                        int ni = i + dir[k][0];
                        int nj = j + dir[k][1];
                        if(ni < 0 || nj < 0 || ni >= grid.size() ||
                        nj >= grid[0].size()) continue;
                        if(grid[ni][nj]){
                            idxs.insert(grid[ni][nj]);
                        }
                    }
                    int temp = 1;
                    set<int>::iterator it = idxs.begin();
                    while(it != idxs.end()){
                        temp += area[*it];
                        it++;
                    }
                    ret = max(ret, temp);
                }
            }
        }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{1,0},{0,1}};
    cout << (ob.largestIsland(v));
}

입력

{{1,0},{0,1}}

출력

복잡도 분석

시간 복잡도는 O(n×m)입니다. DFS가 각 칸을 정확히 한 번씩만 방문하고, 두 번째 순회에서도 각 칸의 네 방향 이웃만 확인하기 때문입니다. 공간 복잡도 역시 O(n×m)으로, 재귀 호출 스택과 섬 넓이를 저장하는 배열이 주요 요소입니다.