LeetCode 130 - Surrounded Regions

Surrounded Regions - LeetCode

 

‘X’, ‘O’로 이루어진 m x n 2차원 배열이 있다.

사방이 ‘X’로 둘러 쌓여있는 ‘O’들은 ‘X’로 변경한 결과를 반환하라.

 

‘X’는 언제 ‘O’로 변경되는가? ‘O’가 ‘X’로 둘러 쌓여 있을 때 변경된다.

가장자리의 ‘O’에 연결된 부분은 절대로 ‘X’로 바뀌지 않는다. 그 이외의 ‘O’들은 전부 ‘X’로 바뀔 수밖에 없다.

즉 가장자리에 존재하는 ‘O’ 부터 시작해서 탐색을 진행하며 해당 위치를 별도로 표기해 두고 나머지를 전부 ‘X’로 채우면 된다.

1. 가장자리를 탐색하면서 ‘O’라면 탐색을 시작한다.
2. 탐색 과정에서는 ‘O’를 임시로 ‘A’로 바꿔놓는다.
3. 모든 탐색이 끝난 후 ‘X’로 가득 차 있는 2차원 배열에서 ‘A’의 위치를 ‘O’로 변경해 리턴한다.

class Solution {
    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public void solve(char[][] board) {
        Set<int[]> startPoints = getStartPoints(board);
        for (int[] startPoint : startPoints) {
            dfs(startPoint, new boolean[board.length][board[0].length], board);
        }

        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (board[r][c] =='O') {
                    board[r][c] = 'X';
                } else if (board[r][c] == 'A') {
                    board[r][c] = 'O';
                }
            }
        }
    }

    private void dfs(int[] currPoint, boolean[][] visited, char[][] board) {
        int r = currPoint[0];
        int c = currPoint[1];
        board[r][c] = 'A';
        visited[r][c] = true;

        for (int d = 0; d < 4; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];

            if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
            if (board[nr][nc] == 'O' && !visited[nr][nc]) {
                dfs(new int[]{nr, nc}, visited, board);
            }
        }
    }

    private Set<int[]> getStartPoints(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        Set<int[]> result = new HashSet<>();
        for (int row : List.of(0, n - 1)) {
            for (int col = 0; col < m; col++) {
                if (board[row][col] == 'O') {
                    result.add(new int[]{row, col});
                }
            }
        }

        for (int col : List.of(0, m - 1)) {
            for (int row = 0; row < n; row++) {
                if (board[row][col] == 'O') {
                    result.add(new int[]{row, col});
                }
            }
        }

        return result;
    }
}