C++로 풀어보는 엔클레이브(Enclaves) 개수 문제

문제 이해하기

2차원 배열 A가 주어져 있습니다. 각 칸은 0(바다) 또는 1(육지)을 나타내며, 이동(move)은 한 육지 칸에서 상하좌우 네 방향 중 하나로 인접한 육지 칸으로 걸어가는 것, 또는 그리드의 경계 밖으로 나가는 것을 의미합니다. 우리가 구해야 하는 값은 아무리 이동해도 그리드 경계 밖으로 나갈 수 없는 육지 칸, 즉 '엔클레이브(enclave)'의 개수입니다.

예시

다음과 같은 그리드가 주어졌다고 가정해 보겠습니다.

0	0	0
1	0	1
0	1	1
0	0	0

이 경우 정답은 3입니다. 0으로 완전히 둘러싸인 1이 세 개 존재하고, 나머지 하나의 1은 경계와 맞닿아 있어 언제든 바깥으로 빠져나갈 수 있기 때문입니다.

접근 방법

핵심 아이디어는 매우 직관적입니다. 경계(테두리)에 위치한 모든 육지 칸에서 DFS를 수행하여, 경계에서 도달 가능한 육지를 모두 0으로 바꿔 버리면 배열에 남아 있는 1의 개수가 곧 엔클레이브의 개수가 됩니다.

구체적인 알고리즘 단계는 다음과 같습니다.

방향 배열 dir을 만들고 [[1,0], [-1,0], [0,1], [0,-1]] 값을 저장합니다.
x, y 좌표와 행렬 A를 인자로 받는 dfs() 함수를 작성합니다.
x < 0 또는 y < 0 또는 x가 A의 행 개수 이상이거나, y가 A의 열 개수 이상이거나, A[x][y]가 0이면 즉시 return 합니다.
A[x][y] := 0으로 설정하여 방문 처리를 합니다.
k를 0부터 3까지 반복하며 nx := dir[k][0] + x, ny := dir[k][1] + y로 두고 dfs(nx, ny, A)를 재귀 호출합니다.
메인 함수에서 ret := 0, n := A의 행 개수로 초기화합니다.
n이 0이 아니면 m := A의 열 개수, 그렇지 않으면 m := 0으로 설정합니다.
i를 0부터 n-1까지 반복하며, A[i][0] == 1이면 dfs(i, 0, A)를 호출하고, A[i][m-1] == 1이면 dfs(i, m-1, A)를 호출합니다. (좌우 경계 처리)
i를 0부터 m-1까지 반복하며, A[0][i] == 1이면 dfs(0, i, A)를 호출하고, A[n-1][i] == 1이면 dfs(n-1, i, A)를 호출합니다. (상하 경계 처리)
마지막으로 전체 배열을 순회하며 남아 있는 1의 개수를 ret에 누적한 뒤 반환합니다.

C++ 구현 코드

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    void dfs(int x, int y, vector<vector<int>>& A){
        if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() ||
        A[x][y] == 0) return;
        A[x][y] = 0;
        for(int k = 0; k < 4; k++){
            int nx = dir[k][0] + x;
            int ny = dir[k][1] + y;
            dfs(nx, ny, A);
        }
    }
    int numEnclaves(vector<vector<int>>& A) {
        int ret = 0;
        int n = A.size();
        int m = n ? A[0].size() : 0;
        for(int i = 0; i < n; i++){
            if(A[i][0] == 1){
                dfs(i, 0, A);
            }
            if(A[i][m - 1] == 1){
                dfs(i, m - 1, A);
            }
        }
        for(int i = 0; i < m; i++){
            if(A[0][i] == 1){
                dfs(0, i, A);
            }
            if(A[n - 1][i] == 1){
                dfs(n - 1, i, A);
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                ret += A[i][j];
            }
        }
        return ret;
    }
};
main(){
    vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
    Solution ob;
    cout << (ob.numEnclaves(v1));
}

입력

[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

출력

복잡도 분석

시간 복잡도: O(n × m) – 각 칸은 최대 한 번만 방문되므로 그리드의 모든 칸을 상수 시간 내에 처리합니다.
공간 복잡도: O(n × m) – 최악의 경우(그리드 전체가 육지일 때) 재귀 호출 스택이 그리드 크기만큼 깊어질 수 있습니다.

마무리

이 문제는 '섬의 개수' 유형 문제의 변형으로, 경계에서 역방향으로 탐색한다는 발상이 핵심입니다. 경계에 붙어 있는 육지만 먼저 제거하면 내부에 고립된 육지를 손쉽게 셀 수 있다는 점을 기억해 두면, 유사한 그리드 탐색 문제(폐쇄 섬 개수 구하기 등)를 풀 때도 큰 도움이 됩니다.

C++로 풀어보는 엔클레이브(Enclaves) 개수 문제 – DFS 완전 정복

문제 이해하기

예시

접근 방법

C++ 구현 코드

입력

출력

복잡도 분석

마무리