leetcode - 130. 둘러싸 인 영역 - 광도 우선 알고리즘 과 깊이 우선 알고리즘

광도 우선 알고리즘 과 깊이 우선 알고리즘 을 다시 만 났 습 니 다.leetcode 주소

         ，   'X'   'O'（   O）。

      'X'      ，           'O'   'X'   。

  :

X X X X
X O O X
X X O X
X O X X

       ，    ：

X X X X
X X X X
X X X X
X O X X

  :
              ，    ，       'O'         'X'。        ，
        'O'     'O'          'X'。                ，
     “  ” 。

제목 의 뜻 은 원래 의 행렬 이 'X' 와 'O' 로 이 루어 져 있다 는 것 이다.여기 O 는 두 가지 유형 이 있 는데,
하 나 는 직접적 이거 나 간접 적 으로 경계 와 연결 되 는 것 이 고 하 나 는 완전히 'X' 에 둘러싸 인 것 이다.
후 자 를 X 로 교체 하 다.
제 가 문 제 를 푸 는 방향 은 첫 번 째 'O' 를 찾 아서 표 시 를 한 다음 에 행렬 을 한 번 옮 겨 다 니 면서 표시 되 지 않 은 'O' 를 'X' 로 바 꾸 는 것 입 니 다.

class Solution {
    int row = 0;
    int col = 0;
    public void solve(char[][] board) {
        if(null == board) return;
        row = board.length;
        if(row == 0) return;
        col = board[0].length;
        if(col == 0) return;
        if(row < 3 || col < 3){ //      ，      ，    
            return;
        }
        //    ,       O
        for(int i = 0; i < col; i++){
            char firstLine = board[0][i];
            if(firstLine == 'O'){
                board[0][i] = '#';
                deal(0, i, board);
            }
            char lastLine = board[row-1][i];
            if(lastLine == 'O'){
                board[row-1][i] = '#';
                deal(row-1, i, board);
            }
        }
        //         
        for(int j = 1; j < row-1; j++){
            char firstCol = board[j][0];
            if(firstCol == 'O'){
                board[j][0] = '#';
                deal(j, 0, board);
            }
            char lastCol = board[j][col -1];
            if(lastCol == 'O'){
                board[j][col -1] = '#';
                deal(j, col-1, board);
            }
        }
        //     O   X,    #   O
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    int[] x = new int[]{1, -1, 0, 0};
    int[] y = new int[]{0, 0, 1, -1};
    Queue<Integer> queue = new LinkedList<>();
    
    /*
    *          O     #
    */
    private void deal(int r, int c,char[][] board){
        queue.add(r*col + c);  //         
        while(queue.size() > 0){
            int temp = queue.remove();
            for(int i = 0; i < 4; i++){ //               
                int rr = x[i] + temp/col;
                int cc = y[i] + temp%col;
                if(rr >= 0 && rr < row && cc >= 0 && cc < col && board[rr][cc] == 'O'){
                    board[rr][cc] = '#';
                    queue.add(rr*col + cc); //           ，    
                }
            }
        }
    }
}

제 가 문 제 를 푸 는 방법 은 바로 표준 적 인 범위 우선 알고리즘 입 니 다. 깊이 우선 알고리즘 은 재 귀 에 사 용 됩 니 다. 여기 서 공식 문 제 를 직접 붙 여 넣 고 관심 이 있 는 것 은 볼 수 있 습 니 다.

class Solution {
    int n, m;

    public void solve(char[][] board) {
        n = board.length;
        if (n == 0) {
            return;
        }
        m = board[0].length;
        for (int i = 0; i < n; i++) {
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 1; i < m - 1; i++) {
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

내 가 전에 발표 한 글 중 에 이 문제 와 생각 이 같다.광도 우선 알고리즘, 깊이 우선 알고리즘 을 더 능숙 하 게 익히 고 싶 은 분 들 은 섬 개 수 를 한 편 더 보 실 수 있 습 니 다.
이 두 가지 지식 점 자 체 는 이해 하기 어렵 지 않 고 많이 연습 하면 파악 하 는 것 이 바로 방법 이다.