[LeetCode#130] Surrounded Regions

 

❐ Description

---

날짜	2024.12.13 (금)
레벨	Medium
링크	https://leetcode.com/problems/surrounded-regions/description
알고리즘 & 자료구조	DFS, Queue
시간 복잡도	O(n•m)

 

예시 이미지

 

 

 

 

 

❐ Approach 1

---

1. 해당 좌표를 방문한 이력이 없고, Land(O)인 부분 부터 탐색을 시작한다.
2. 동서남북 방향으로 DFS를 실행한다.
   • 현재 위치를 WALL(X)로 변경한다.
   • Queue에 현재 위치를 담는다.
   • 현재 위치를 방문 처리한다. ➔ 순회를 최적화하기 위함.
3. 동서남북이 WALL(X)로 둘러 쌓여 있지 않은 경우
   • Queue에 있는 모든 좌표를 Land(O) 표시로 변경한다.

public void solve(char[][] board) {
    int maxRow = board.length;
    int maxCol = board[0].length;
    boolean[][] visited = new boolean[maxRow][maxCol];

    for (int row = 0; row < maxRow; row++) {
        for (int col = 0; col < maxCol; col++) {
            if (board[row][col] == LAND && !visited[row][col]) {
                Queue<int[]> q = new LinkedList<>();
                if (!(dfs(board, visited, q, row, col))) {
                    while (!q.isEmpty()) {
                        int[] poll = q.poll();
                        board[poll[0]][poll[1]] = LAND;
                    }
                }
            }
        }
    }
}

private boolean dfs(char[][] board, boolean[][] visited, Queue<int[]> q, int row, int col) {
    int maxRow = board.length;
    int maxCol = board[0].length;

    if (row < 0 || col < 0 || row >= maxRow || col >= maxCol) {
        return false;
    }

    if (board[row][col] == WALL) {
        return true;
    }

    q.offer(new int[]{row, col});
    board[row][col] = WALL;
    visited[row][col] = true;
    boolean left = dfs(board, visited, q, row, col - 1);
    boolean right = dfs(board, visited, q, row, col + 1);
    boolean up = dfs(board, visited, q, row - 1, col);
    boolean down = dfs(board, visited, q, row + 1, col);
    return left && right && up && down;
}

 

 

 

 

 

 

❐ Approach 2

---

두 번째 접근은 사각형의 테두리만 확인하는 방법이다. 잘 생각해보면 테두리가 모두 WALL이라면 내부는

신경쓰지 않아도 되기 때문이다. 그리고 만약 테두리 중에 Land가 있다면 이는 모든 면이 Wall로 둘러 쌓이지

않았음을 확신할 수 있다.

 

private static final char WALL = 'X';
private static final char LAND = 'O';

public void solve(char[][] board) {
    int maxRow = board.length, maxCol = board[0].length;
    boolean[][] vis = new boolean[maxRow][maxCol];
    for (int i = 0; i < maxRow; i++) {
        if (board[i][0] == 'O' && !vis[i][0]) {
            dfs(board, vis, i, 0);
        }
        if (board[i][maxCol - 1] == LAND && !vis[i][maxCol - 1]) {
            dfs(board, vis, i, maxCol - 1);
        }
    }
    for (int i = 0; i < maxCol; i++) {
        if (board[0][i] == LAND && !vis[0][i]) {
            dfs(board, vis, 0, i);
        }
        if (board[maxRow - 1][i] == LAND && !vis[maxRow - 1][i]) {
            dfs(board, vis, maxRow - 1, i);
        }
    }
    for (int row = 0; row < maxRow; row++) {
        for (int col = 0; col < maxCol; col++) {
            if (!vis[row][col])
                board[row][col] = WALL;
        }
    }
}

public void dfs(char[][] board, boolean[][] vis, int row, int col) {
    vis[row][col] = true;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] dir : dirs) {
        int nextRow = row + dir[0];
        int nextCol = col + dir[1];
        if (positionInRage(board, nextRow, nextCol) &&
                isLand(board, vis, nextRow, nextCol) &&
                visited(vis, nextRow, nextCol)) {
            dfs(board, vis, nextRow, nextCol);
        }
    }
}

private boolean positionInRage(char[][] board, int row, int col) {
    return row >= 0 && col >= 0 && row < board.length && col < board[0].length;
}

private boolean isLand(char[][] board, boolean[][] vis, int row, int col) {
    return board[row][col] == LAND;
}

private boolean visited(boolean[][] vis, int row, int col) {
    return !vis[row][col];
}

 

 

 

 

 

---