[LeetCode] 130. Surrounded Regions

Problem

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

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example 1:

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: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

Example 2:

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

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.

---

Solution

class Solution {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0)
            return;
        if (board.length < 3 || board[0].length < 3)
            return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O')
                helper(board, i, 0);
            if (board[i][n - 1] == 'O')
                helper(board, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            if (board[0][j] == 'O')
                helper(board, 0, j);
            if (board[m - 1][j] == 'O')
                helper(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '*')
                    board[i][j] = 'O';
            }
        }
    }
    private void helper(char[][] board, int r, int c) {
        if (r < 0 ||
            c < 0 ||
            board.length - 1 < r ||
            board[0].length - 1 < c ||
            board[r][c] != 'O')
            return;
        board[r][c] = '*';
        helper(board, r + 1, c);
        helper(board, r - 1, c);
        helper(board, r, c + 1);
        helper(board, r, c - 1);
    }
}

Explanation

• Board 가장자리의 ‘O’와 연결된 ‘O’를 제외한 나머지 ‘O’를 ‘X’로 교체해야 하는데, ‘O’가 얼마나 길게 연결되어 있을지 알 수 없기 때문에, 재귀함수 호출을 중단하는 조건문을 가진 재귀함수를 선언하여 알고리즘을 작성해 변경작업을 반복적으로 수행하도록 한다.
• 재귀함수를 호출할 때마다 ‘O’를 ‘X’로 변경하면 원하는 결과가 나오지 않을 수 있기 때문에, ‘O’를 ‘X’가 아닌 ‘*‘로 임시로 변경하도록 한다.

  private void helper(char[][] board, int r, int c) {
    if (r < 0 ||
        c < 0 ||
        board.length - 1 < r ||
        board[0].length - 1 < c ||
        board[r][c] != 'O')
        return;
    board[r][c] = '*';
    helper(board, r + 1, c);
    helper(board, r - 1, c);
    helper(board, r, c + 1);
    helper(board, r, c - 1);
  }
  

• 재귀함수를 호출하기 전에 변수 길이를 줄여 가독성을 높이기 위해 따로 변수 m과 n을 선언하여 사용하도록 한다.

  int m = board.length;
  int n = board[0].length;
  

• Board의 가장자리에서만 재귀함수를 호출하면 되므로, 가장자리를 담당하는 열 또는 행 어느 곳 먼저 재귀함수를 실행해도 상관없다. 가장자리 열부터 재귀함수를 호출하도록 for 반복문을 작성한다.

  for (int i = 0; i < m; i++) {
    if (board[i][0] == 'O')
        helper(board, i, 0);
    if (board[i][n - 1] == 'O')
        helper(board, i, n - 1);
  

• 다음은 가장자리를 담당하는 행에서 재귀함수를 호출하여야 하는데, 가장자리 열에서 재귀함수를 호출할 때, 가장자리 행의 첫번째 요소와 마지막 요소에서도 재귀함수가 실행되는 꼴이기 때문에, 가장자리 행의 첫번째 요소와 마지막 요소를 제외하고 재귀함수가 호촐될 수 있도록 for 반복문을 작성한다.

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (board[i][j] == 'O')
            board[i][j] = 'X';
        if (board[i][j] == '*')
            board[i][j] = 'O';
    }
  

• 가장자리 열과 행에서 재귀함수를 호출하여 조건에 해당하는 ‘O’가 모두 ‘*‘로 변경되었다. 이제 모든 ‘*‘를 다시 ‘O’로 변경해주도록 for 반복문을 작성한다.

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (board[i][j] == 'O')
            board[i][j] = 'X';
        if (board[i][j] == '*')
            board[i][j] = 'O';
    }
  }