문제 소개
2차원 격자(grid)가 주어진다고 가정해 보겠습니다. 이 격자는 0(육지)과 1(물)로만 구성되어 있습니다. 여기서 섬(island)은 0들이 상하좌우 네 방향으로 연결되어 이루는 최대 그룹을 의미하고, 폐쇄된 섬(closed island)은 사방이 물(1)로 완전히 둘러싸여 있는 섬을 말합니다. 우리의 목표는 이러한 폐쇄된 섬의 개수를 구하는 것입니다.
예를 들어 다음과 같은 격자가 있다고 해봅시다.
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
이 경우 출력값은 2입니다. 격자 내부에 물에 완전히 둘러싸인 섬이 두 개 존재하기 때문입니다. 반면, 격자의 가장자리와 맞닿아 있는 육지는 외부와 연결되어 있으므로 폐쇄된 섬으로 간주하지 않습니다.
해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 섬을 탐색하면서 그 섬이 격자의 경계 밖으로 뻗어 나가는지 여부를 추적하는 것입니다. 단계별로 살펴보겠습니다.
- 섬이 경계에 닿았는지 여부를 추적하는
flag변수를 정의합니다. dfs라는 메서드를 정의합니다. 이 메서드는 격자 g, 현재 좌표 i, j, 그리고 격자의 크기 n, m을 인자로 받습니다.- 좌표 (i, j)가 격자 범위를 벗어나면 flag를 false로 설정하고 탐색을 종료합니다. 이는 해당 섬이 외부와 연결되어 폐쇄된 섬이 아니라는 의미입니다.
- g[i][j]가 1(물)이거나 이미 방문한 -1이라면 그대로 반환합니다.
- g[i][j]가 0(육지)이라면 -1로 표시하여 방문 처리합니다.
- 상하좌우 네 방향으로 재귀적으로 dfs(g, i+1, j, n, m), dfs(g, i, j+1, n, m), dfs(g, i-1, j, n, m), dfs(g, i, j-1, n, m)을 호출합니다.
메인 로직
- n × m 크기의 dp 행렬을 생성하고 모든 값을 -1로 초기화합니다.
- i를 0부터 n-1까지, j를 0부터 m-1까지 순회하면서 g[i][j]가 0인 지점을 발견하면:
- flag를 true로 설정한 뒤 dfs(g, i, j, n, m)을 호출합니다.
- 탐색이 끝나면 ans에 flag 값을 더합니다. 탐색 중 경계에 닿았다면 flag가 false가 되어 카운트되지 않습니다.
- 최종적으로 ans를 반환합니다.
이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector < vector <int> > dp;
bool flag;
void dfs(vector<vector<int>>& g, int i, int j, int n, int m){
if(i>=n || j >=m || i<0 || j<0){
flag = false;
return ;
}
if(g[i][j] == 1 || g[i][j] == -1)return;
if(g[i][j] == 0)g[i][j] = -1;
dfs(g, i+1, j, n, m);
dfs(g, i, j+1, n, m);
dfs(g, i-1, j, n, m);
dfs(g,i, j-1, n, m);
}
int closedIsland(vector<vector<int>>& g) {
int ans = 0;
int n = g.size();
int m = g[0].size();
dp = vector < vector <int> > (n, vector <int> (m, -1));
for(int i = 0; i < n ; i++){
for(int j = 0; j < m; j++){
if(g[i][j] == 0){
flag = true;
dfs(g, i , j ,n ,m);
ans += flag;
}
}
}
return ans;
}
};
main(){
vector<vector<int>> v =
{{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0
,1},{1,1,1,1,1,1,1,0}};
Solution ob;
cout << (ob.closedIsland(v));
}
입력
[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
출력
2
복잡도 분석
시간 복잡도는 격자의 모든 칸을 한 번씩만 방문하므로 O(n×m)입니다. 공간 복잡도 역시 재귀 호출 스택이 최악의 경우 격자 전체 칸 수만큼 깊어질 수 있어 O(n×m)입니다. 이처럼 DFS 기반 접근은 각 육지 칸을 정확히 한 번씩 처리하므로 매우 효율적입니다.