솔루션 개발:

질문

이 기사에서는 Leetcode의 '130. Surrounded Regions' 질문을 다룰 것입니다.

의문:

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally > surrounded by 'X'.

영역은 둘러싸인 영역에서 모든 'O' s를 'X' s로 뒤집음으로써 캡처됩니다.

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.

질문 설명

이 질문의 등급은 보통입니다. 대부분 정확합니다. 그러나 이것은 Graph Theory에서 깊이 우선 검색 또는 너비 우선 검색을 잘 이해하고 있는 경우에만 매체입니다. 뿐만 아니라 이러한 아이디어를 매트릭스에 적용하는 방법을 알고 있습니다. 이러한 작업을 수행하는 방법을 모르면 이 문제를 해결하는 데 어려움을 겪을 것입니다.

우리는 행렬을 받았고, 행렬의 가장자리에 접하지 않는 모든 영역을 캡처하라는 지시를 받았습니다.
언뜻 보기에 이 질문은 간단합니다. 깊이 우선 검색을 실행하고 가장자리에 접하는 것이 있는지 확인하세요. 그렇다면 우리는 그 지역이 둘러싸여 있다는 것을 압니다. 그렇지 않은 경우 해당 지역이 둘러싸여 있지 않다는 것을 알 수 있습니다.

권장 지식

Graph Theory

Matrixes

Depth First Search

우리는 무엇을 알고 있습니까?

'X'와 'O'로 가득 찬 행렬이 있습니다

.

M x N 매트릭스입니다

.

둘러싸인 모든 영역을 'X'로 변환해야 합니다

.

어떻게 할 것인가:

우리는 'X'로 둘러쌀 수 없는 모든 잘못된 섬이 행렬의 가장자리에 연결되어 있음을 알고 있습니다. 그래서 먼저, 우리는 주어진 노드 중 하나가 'O'인지 묻는 행렬의 모든 경계를 방문할 것입니다. 그들이 유효하지 않다는 것을 이미 알고 있다면 전체 섬을 'T' 의미로 표시합니다. 온도 나중에 변환을 취소할 것이기 때문입니다.

유효하지 않은 섬을 모두 표시하면 'T'가 아닌 모든 지역을 자동으로 캡처합니다. 모든 임시 영역은 원래 'O' 상태로 다시 변환됩니다.

유효하지 않은 섬을 찾기 위해 행렬의 모든 가장자리를 실행합니다.

유효하지 않은 섬에서 깊이 우선 검색을 수행하고 유효하지 않은 섬을 'T'로 표시합니다.

전체 매트릭스를 실행하고 'T'가 아닌 모든 영역을 자동으로 캡처합니다

.

그런 다음 모든 'T' 영역을 다시 'O'로 변환합니다

.

빅오 표기법:

시간 복잡도: O((V * E) + b)/O(n) | 여기서 n은 매트릭스의 노드 수입니다. 행렬의 모든 노드를 방문할 것입니다. 여기서 V는 그래프의 노드 수이고 E는 그래프의 가장자리 수입니다. 여기서 b는 행렬의 경계를 나타냅니다. 최악의 경우와 마찬가지로 각 노드와 꼭지점을 방문할 것입니다. 이는 전체 행렬이 하나의 섬임을 의미합니다.

공간 복잡도: O(h) | 깊이 우선 검색을 수행하기 위해 호출 스택 내에 모든 노드를 저장하므로 h는 경계 섬 내의 가장 큰 노드 수입니다.

해결책

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {

    /* -------------------------------------------------------------------------- */
    /*                          130. Surrounded Regions                           */
    /* -------------------------------------------------------------------------- */

    /* ---------------------------- Solution Concept ---------------------------- */

    // We need to capture all regions that are not bordered to the edge of the matrix.
    // We could perform Depth First Search on all the cells in the matrix and ask
    // if any of them border the edge. Instead, we're going to do all the edges
    // of the matrix and convert all island that border the island to temp nodes.
    // We do this because we already know that the bad nodes border the edge 
    // of the matrix.

    // Once we've marked all the bad islands. We run through the entire matrix
    // automatically capturing all the nodes that are not marked as bad. And all
    // the previously marked bad nodes are converted to back to islands.

    /* ---------------------------- Solution as Code ---------------------------- */

    // Matrix Maxes (Makes our life's easier)
    const max_rows = board.length - 1;
    const max_cols = board[0].length - 1;

    // During our search, we can go up, down, left and right.
    // We cannot go diagonally! We can only go up, down, left and right.
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    // Our helper depth first function that converts all bad
    // islands to marked nodes.
    const depth_first_search = (row_index, col_index) => {

        // Is it within bounds of the matrix?
        // And are we allowed to do dfs on this node?
        if (row_index > max_rows || col_index > max_cols || col_index < 0 || row_index < 0 || board[row_index][col_index] != "O"){
            return false
        }

        // So node is within bounds, it bordered the edges of the matrix
        // and thus it's a invalid island. As we cannot Surround the Region
        // So let's mark it as a 't'. We do this to let us know not to 
        // convert this node into a 'x'.

        board[row_index][col_index] = "T";

        // Search in all directions for the rest of the island.
        for (const [x, y] of directions){
            depth_first_search(row_index + x, col_index + y);
        }
    }


    // let's check all the edges of the matrix checking 
    // for these bad nodes. If we ever find one, we run 
    // DFS on it to mark it. Starting with:

    // Top and Bottom of matrix
    for (let i = 0; i <= max_cols ; i++){
        const top = board[0][i];
        const bottom = board[max_rows][i];

        if (top === "O"){
            depth_first_search(0, i);
        }

        if (bottom === "O"){
            depth_first_search(max_rows, i);
        }
    }

    // Left and Right of matrix
    for (let i = 0; i <= max_rows ; i++){
        const left = board[i][0];
        const right = board[i][max_cols];

        if (left === "O"){
            depth_first_search(i, 0);
        }

        if (right === "O"){
            depth_first_search(i, max_cols);
        }
    }

    // Now we have gone through the entire border of the matrix
    // we have now marked all bad islands if their was any.
    // Meaning we can automatically capture all regions that 
    // didn't border that edge.

    // We will also unmark all the marked nodes that did border 
    // the edge of the matrix. We do this because we know that it's an invalid island.
    board.forEach((row, row_index) => {
        row.forEach((col, col_index) => {

            // Capture unmarked regions.
            if (col === "O") board[row_index][col_index] = "X"

            // Converted marked regions back to a normal island
            if (col === "T") board[row_index][col_index] = "O"
        })
    })

    // Return Nothing. We modified our input in place.

};