[코딩 면접] 아마존 인터뷰 준비 - Number of Islands

처음 이 문제를 풀었을 때, 저는 이중 for 루프로 '1'을 발견할 때마다 카운트를 올렸습니다. 결과는 당연히 틀렸고, "연결된 섬을 하나로 세지 못하는" 근본적인 오류를 한참 뒤에야 알아챘습니다. 그 뒤 DFS를 붙였는데, 이번엔 방문 처리를 빠뜨려서 재귀가 무한 루프에 빠지는 사태가 났습니다. Stack Overflow 에러 메시지를 면접관 화면에 띄워놓고 얼어버린 그 순간이 아직도 생생합니다.

LeetCode 토론을 보면 이 문제에서 사람들이 반복하는 실수가 크게 세 가지입니다. 방문 체크 누락으로 인한 무한 루프, 경계 체크보다 값 체크를 먼저 해서 생기는 배열 인덱스 초과, 그리고 섬을 발견할 때마다 카운트를 올리는 것이 아니라 탐색을 시작할 때 한 번만 올려야 한다는 사실을 놓치는 것입니다. 오늘은 이 세 함정을 직접 경험한 이야기부터 시작해보겠습니다.

문제 설명

주어진 2차원 배열은 "1"과 "0"으로 채워져 있습니다. "1"은 섬을 뜻하고 "0"은 물을 뜻합니다. 섬은 물로 둘러싸여 있으며 가로나 세로로 다른 섬과 연결되어 있는 경우를 뜻합니다. (대각선은 인정하지 않음) 가장자리는 모두 물이라고 가정하여도 좋습니다. 섬의 개수를 모두 구하는 것이 문제라 할 수 있습니다.

예제 1:
Input: grid =
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
Output: 1

예제 2:
Input: grid =
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
Output: 3

제가 밟은 세 가지 지뢰

문제를 처음 볼 때 가장 먼저 저지른 실수는 카운트를 잘못 증가시키는 것이었습니다. 이중 for 루프를 돌면서 '1'을 만날 때마다 count++을 했는데, 이렇게 하면 하나로 연결된 넓은 섬도 셀 하나마다 따로 세게 됩니다. 예제 1의 정답이 1인데, 9가 나왔습니다.

DFS를 추가한 뒤에는 방문 처리를 빠뜨렸습니다. '1'에서 DFS를 시작하면 상하좌우를 탐색하는데, 방문한 셀을 표시하지 않으니 탐색이 왔던 길로 되돌아가면서 무한 루프에 빠졌습니다. Java에서는 이게 StackOverflowError로 이어집니다. 실제 면접에서 이 에러를 보여줬을 때 면접관이 조용히 "방문 처리를 어떻게 하셨어요?"라고 물었고, 그제야 빠진 걸 깨달았습니다.

세 번째 함정은 경계 체크와 값 체크의 순서입니다. 처음에 이렇게 짰습니다.

// 잘못된 순서 — 배열 경계 밖을 먼저 접근하면 ArrayIndexOutOfBoundsException
if (grid[row][col] != '1' || row < 0 || ...) return;

배열 범위를 벗어난 인덱스로 grid[row][col]에 접근하는 순간 예외가 납니다. 반드시 경계 체크를 먼저 해야 합니다.

접근 방법

이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.

1. 2차원 배열을 이중 for-loop을 사용해서 모든 원소를 방문합니다.
2. "1"을 발견하면 DFS 알고리즘을 시작해 연결된 모든 '1' 셀을 탐색합니다. 이때 count를 딱 한 번 증가시킵니다.
3. 방문한 셀을 기억하기 위해 "2"로 변경합니다. 이게 핵심입니다. 추가 메모리 없이 원본 배열을 활용해 방문 여부를 표시합니다.
4. 모든 연결된 섬을 방문한 다음 섬의 개수를 증가합니다.
5. 배열을 모두 방문했으면 섬의 개수를 반환합니다.

여기서 알아두어야 할 중요한 점은 방문한 "1"을 "2"로 변경하는 것이라 할 수 있습니다. 이 방식은 추가적인 메모리를 사용하지 않고 풀 수 있어서 공간 복잡도를 O(1)으로 유지할 수 있습니다.

DFS 기반 해결 코드

private int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

public int numIslands(char[][] grid) {
    int count = 0;
    for(int i = 0; i < grid.length; i++){
        for(int j = 0; j < grid[i].length; j++){
            if(grid[i][j] == '1'){
                dfs(grid, i, j);
                count++;  // 새로운 섬 발견 시 딱 한 번만 증가
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int row, int col) {
    // 경계 체크를 반드시 먼저, 그 다음 값 체크
    if(row < 0 || row >= grid.length || col < 0 || col >= grid[row].length || grid[row][col] != '1') 
        return;
    grid[row][col] = '2';  // 방문 표시 — 이걸 빠뜨리면 무한 루프
    for(int[] dir : dirs){
        dfs(grid, row + dir[0], col + dir[1]);
    }
}

DFS 함수의 첫 줄을 보면 경계 체크(row < 0 등)가 값 체크(grid[row][col] != '1')보다 먼저 오는 것을 확인할 수 있습니다. 이 순서를 바꾸면 배열 범위 밖에서 값을 읽으려다 ArrayIndexOutOfBoundsException이 납니다. 그리고 grid[row][col] = '2'는 절대 빠뜨리면 안 됩니다. 이게 없으면 탐색이 무한 루프에 빠집니다.

알고리즘 분석

이 알고리즘의 시간 복잡도는 O(N×M)로 분석됩니다. (N은 행의 수, M은 열의 수) 각 셀을 한 번씩 방문하기 때문에 공간 복잡도는 O(1)으로 유지할 수 있습니다. 추가적인 메모리를 사용하지 않고 input 배열을 재활용하기 때문입니다. 단, 재귀 깊이는 최대 N×M이므로 콜 스택 공간은 O(N×M)까지 늘어날 수 있다는 점을 면접에서 언급하면 가산점을 받을 수 있습니다.

면접 팁

면접에서 이 문제를 만나면 다음 사항을 유의하세요.

1. 방문 체크 방법: 추가 메모리를 사용하지 않고 input 배열을 '2'로 수정하는 방법을 설명합니다. "원본 배열을 수정해도 됩니까?"라고 면접관에게 먼저 확인하는 자세가 좋습니다.
2. 경계 체크 순서: 반드시 배열 범위 검사를 먼저, 값 비교를 나중에 해야 한다고 설명하세요. 순서가 바뀌면 런타임 에러가 납니다.
3. 카운트 시점: '1'을 발견하는 즉시 count++하고 DFS로 연결된 모든 셀을 '2'로 마킹합니다. DFS 내부에서는 카운트를 올리지 않습니다.
4. edge case: 빈 배열, 모든 0, 모든 1 등 다양한 경우를 고려합니다. if (grid == null || grid.length == 0) return 0;을 맨 앞에 두는 것을 잊지 마세요.
5. 최적화: Union-Find 자료구조로도 풀 수 있습니다. 면접관에게 두 방법 모두 설명할 수 있으면 더 좋습니다. BFS 버전은 큐를 사용해 재귀 스택 깊이 문제를 피할 수 있다는 것도 덧붙이세요.

이 문제는 단순히 섬을 세는 것을 넘어 플러드 필(Flood Fill) 패턴의 원형입니다. 이미지 편집기의 페인트 버킷 기능, 미로 탈출, 영역 감지 등 수많은 실무 문제가 이 패턴 위에 세워져 있습니다. 면접에서 "이 알고리즘이 실제로 어디 쓰이나요?"라는 질문이 나오면 자신 있게 대답할 수 있도록 준비해두세요.