알고리즘 문제 풀이

[LeetCode] 130. Surrounded Regions

_OB1N 2021. 11. 1. 11:40

문제 출처: https://leetcode.com/problems/surrounded-regions/

 

Surrounded Regions - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


문제

'X'와 'O'로 구성된 $m x n$ 행렬 'board'가 주어지면, 사면이 'X'로 둘러싸인 지역을 찾아라.

 

찾아진 지역의 모든 'O'를 'X'로 바꾸어라.

예제

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation: Surrounded regions should not be on the border, 
which means that any 'O' on the border of the board are not flipped to 'X'. 
Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. 
Two cells are connected if they are adjacent cells connected horizontally or vertically.
Input: board = [["X"]]
Output: [["X"]]

풀이

위 주어진 예제의 설명에서 문제 풀이의 핵심이 될 수 있는 힌트를 얻을 수 있습니다.

 

예제의 설명을 보면, 사면이 'X'로 둘러쌓이지 않으려면 지역이 board의 경계에 맞닿아 있어야 한다는 말이 언급되어 있습니다. 이것이 문제 풀이의 핵심입니다.

 

그래서 저는 board의 경계 지점에 맞닿아있는 영역을 탐색하고, 찾아진 영역이 아닌 다른 영역은 모두 'X'로 둘러싸인 영역으로 취급하여 'O'를 'X'로 바꾸는 작업을 수행하는 방식으로 알고리즘을 작성하였습니다.

 

기본적인 틀을 작성해보겠습니다.

var solve = function(board) {
    const M = board.length;
    const N = board[0].length;
    
    // 외곽과 연결된 영역을 체크하여 기록하는 배열
    const visited = new Array(M).fill(0).map(val => new Array(N).fill(false));
    
    // 상하단 외곽 탐색
    for (let col = 0; col < N; col++) {
        if (board[0][col] === 'O' && !visited[0][col]) { ... }
        if (board[M-1][col] === 'O' && !visited[M-1][col]) { ... }
    }
    
    // 좌우 외곽 탐색
    for (let row = 1; row < M-1; row++) {
        if (board[row][0] === 'O' && !visited[row][0]) { ... }
        if (board[row][N-1] === 'O' && !visited[row][N-1]) { ... }
    }
    
    // 실제 board에 결과 반영
    for (let row = 0; row < M; row++) {
        for (let col = 0; col < N; col++) {
            if (board[row][col] === 'O' && !visited[row][col]) { board[row][col] = 'X'; }
        }
    }
}

우선, visited 배열이 있습니다. 이 배열은 board에 존재하는 영역 중 경계에 맞닿아 있는 영역을 기록하는 배열입니다. 이후 탐색 과정에서 동일한 영역을 반복 탐색하는 불필요한 작업을 예방하는 역할도 수행하게 됩니다.

 

아래 두 반복문이 실질적으로 board의 외곽을 탐색하는 코드입니다. 외곽을 탐색하면서 'O'로 체크된 곳을 찾으면서 visited 배열에 아직 체크되지 않은 지역만을 탐색합니다. 이러한 조건에 만족하는 지점을 찾게 되면 해당 지점에서 시작하여 이 영역의 범위를 탐색해 visited에 저장하는 작업이 필요합니다. 현재는 비워두었습니다.

 

마지막으로는 visited에 기록된 정보를 바탕으로 실제 board에 결과를 반영하는 코드입니다.

 

이제 비워두었던 부분을 채워보도록 하겠습니다.

 

해당 부분에서 해야하는 과정을 생각해보면, 한 지점의 상하좌우, 네 방향을 살펴보고 'O'인 지점이 있다면 해당 지점으로 가서 다시 상하좌우를 살피는 과정을 반복하는 것을 통해 인접해 있는 모든 'O'를 찾을 수 있습니다.

 

조금 더 알고리즘적으로 이야기하면, 현재 문제를 그래프 탐색 문제로 볼 수 있고 이를 DFS나 BFS 기법을 통해 'O'로 연결된 영역을 특정 지을 수 있습니다.

 

저는 BFS 기법을 사용하여 코드를 작성하였습니다.

function bfs(board, visited, [row, col]) {
    const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    
    const q = [[row, col]];
    visited[row][col] = true;
    
    while (q.length) {
    	const cur = q.shift();
        
        dir.forEach(d => {
            const nextRow = cur[0] + d[0];
            const nextCol = cur[1] + d[1];
            
            if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length) { return; }
            if (board[nextRow][nextCol] === 'X' || visited[nextRow][nextCol]) { return; }
            
            visited[nextRow][nextCol] = true;
            q.push([nextRow, nextCol]);
        });
    }
}

작성한 bfs를 사용하여 비워두었던 코드를 채워보도록 하겠습니다.

var solve = function(board) {
    const M = board.length;
    const N = board[0].length;
    
    const visited = new Array(M).fill(0).map(val => new Array(N).fill(false));
    
    for (let col = 0; col < N; col++) {
        if (board[0][col] === 'O' && !visited[0][col]) { bfs(board, visited, [0, col]) }
        if (board[M-1][col] === 'O' && !visited[M-1][col]) { bfs(board, visited, [M-1, col]) }
    }
    
    for (let row = 1; row < M-1; row++) {
        if (board[row][0] === 'O' && !visited[row][0]) { bfs(board, visited, [row, 0]) }
        if (board[row][N-1] === 'O' && !visited[row][N-1]) { bfs(board, visited, [row, N-1]) }
    }
    
    for (let row = 0; row < M; row++) {
        for (let col = 0; col < N; col++) {
            if (board[row][col] === 'O' && !visited[row][col]) { board[row][col] = 'X'; }
        }
    }
}

이 코드의 시간 복잡도는 BFS에 의존하고 있습니다.

 

외곽 탐색 자체는 내부적으로 상수 시간에 해결 가능하다고 가정하면 $O(M)$과 $O(N)$입니다. 그리고 실제 board에 반영하는 코드 또한 $O(MN)$이 될 것입니다. 문제는 외곽을 탐색이 실제로는 영역을 찾는 문제로 BFS 알고리즘을 통해서 수행된다는 것입니다.

 

BFS는 최대 $O(V+E)$ (V = 정점 수, E = 간선 수)인데, 이 문제에서 정점은 board의 셀 수인 $MN$개이고 간선은 $2MN-M-N$개 입니다. 즉, $O(MN)$이 BFS의 시간 복잡도가 됩니다.

 

BFS의 최악의 케이스를 상정하면 모든 board가 'O'인 케이스를 생각할 수 있고, 이 경우 외곽 탐색 과정에서 BFS 알고리즘은 딱 한 번 동작하게 될 것입니다. 이를 고려하면 전체 알고리즘의 시간 복잡도가 $O(MN)$이라 할 수 있습니다.

 

Github: 130.js

 

GitHub - opwe37/Algorithm-Study

Contribute to opwe37/Algorithm-Study development by creating an account on GitHub.

github.com