문제 접근 방식
2차원 격자(grid) 맵을 선형으로 스캔하면서, 어떤 노드의 값이 '1'이면 그 노드를 깊이 우선 탐색(Depth First Search, DFS)을 시작하는 루트 노드로 간주합니다. DFS가 진행되는 동안 방문한 모든 노드는 '0'으로 설정하여 방문 처리를 합니다.
DFS를 트리거하는 루트 노드의 개수를 세면 그 값이 곧 섬의 총 개수가 됩니다. 각 DFS 시작점이 하나의 섬을 식별하기 때문입니다. 즉, 상하좌우로 연결된 '1'들은 하나의 덩어리(섬)로 묶이고, 서로 분리된 덩어리의 수가 정답이 됩니다.
알고리즘 단계
1단계: 격자의 모든 칸을 순서대로 확인합니다.
2단계: 현재 칸이 '1'이고 아직 방문하지 않았다면, 새로운 섬을 발견한 것이므로 결과 카운트를 1 증가시킵니다.
3단계: 해당 위치에서 DFS를 수행하여 상하좌우로 인접한 모든 육지('1')를 재귀적으로 방문하고 방문 표시를 합니다.
4단계: 격자 전체를 탐색할 때까지 반복한 뒤, 최종 카운트를 반환합니다.
예제 코드
using System;
namespace ConsoleApplication{
public class Matrix{
public int PrintNumberOfIslands(char[] grid){
bool[] visited = new bool[grid.GetLength(0), grid.GetLength(1)];
int res = 0;
for (int i = 0; i < grid.GetLength(0); i++){
for (int j = 0; j < grid.GetLength(1); j++){
if (grid[i, j] == '1' && !visited[i, j]){
DFS(grid, visited, i, j);
res++;
}
}
}
return res;
}
public void DFS(char[] grid, bool[] visited, int i, int j){
if (i < 0 || i >= grid.GetLength(0)) return;
if (j < 0 || j >= grid.GetLength(1)) return;
if (grid[i, j] != '1' || visited[i, j]) return;
visited[i, j] = true;
DFS(grid, visited, i + 1, j);
DFS(grid, visited, i - 1, j);
DFS(grid, visited, i, j + 1);
DFS(grid, visited, i, j - 1);
}
}
class Program{
static void Main(string[] args){
Matrix m = new Matrix();
char[] mm = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' }, { '0', '0', '0', '0', '1' } };
Console.WriteLine(m.PrintNumberOfIslands(mm));
}
}
}출력 결과
2
복잡도 분석
시간 복잡도: O(M × N) — 격자의 모든 칸을 최대 한 번씩만 방문하므로 행의 개수 M과 열의 개수 N에 비례합니다.
공간 복잡도: O(M × N) — 방문 여부를 저장하는 불리언 배열이 격자와 같은 크기로 필요합니다. 최악의 경우(격자 전체가 육지인 경우) 재귀 호출 스택의 깊이 역시 O(M × N)까지 늘어날 수 있습니다.
마무리
이 문제는 대표적인 그래프 탐색 응용 문제로, BFS(너비 우선 탐색)나 Union-Find 알고리즘으로도 해결할 수 있습니다. 다만 DFS를 사용하면 코드가 간결해지고 직관적이라 면접에서 구현하기에 적합합니다. 추가로, 방문 배열 대신 원본 격자의 값을 직접 '0'으로 변경하면 별도의 메모리 없이 문제를 해결할 수 있다는 점도 기억해 두면 좋습니다.