[LeetCode] 130. Surrounded Regions - 넓이우선탐색(BFS) + 구현(Implementation) JAVA

https://leetcode.com/problems/surrounded-regions/description/

코드설명

넓이우선탐색(BFS) + 구현(Implementation) 을 활용합니다.

 

문제에 주어진대로, "O"를 돌면서 인접한 곳에 "O"을 BFS로 탐색합니다.

이떄, 탐색 중에 가장 바깥(r == 0 || r == Board.length - 1 || c == 0 || c == Board[0].length) 에 도달한다면, 해당 칸은 SurroundedRegion이 아닙니다.

 

만약 SurroundedRegion이라면(즉, 바깥과 연결되어있지 않고 X로 둘러쌓여있다면), 해당 칸을 모두 "X"로 표시합니다.

코드

class Solution {
    boolean[][] visited;
    public void solve(char[][] board) {
        visited = new boolean[board.length][board[0].length];
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                char temp = board[i][j];
                if(temp == 'O' && visited[i][j] == false){
                    BFS(i, j, board);
                }
            }
        }
    }

    void BFS(int sR, int sC, char[][] board){
        Stack<Node> st = new Stack<>();
        Queue<Node> q = new LinkedList<>();
        Node nowNode = new Node(sR, sC);
        q.offer(nowNode);
        st.push(nowNode);
        visited[sR][sC] = true;
        boolean isSurrounded = true;
        while(!q.isEmpty()){
            Node temp = q.poll();
            int r = temp.r;
            int c = temp.c;
            for(int[] dir : new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}){
                int nr = r + dir[0];
                int nc = c + dir[1];

                if(nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length ) {
                    isSurrounded = false;
                    continue;
                }
                if(visited[nr][nc] == true) continue;
                if(board[nr][nc] == 'X') continue; 
                visited[nr][nc] = true;
                Node newNode = new Node(nr, nc);
                q.offer(newNode);
                st.push(newNode);
            }
        }

        if(isSurrounded == true){
            while(!st.isEmpty()){
                Node temp = st.pop();
                board[temp.r][temp.c] = 'X';
            }
        }

    }
}
class Node{
    int r;
    int c;
    public Node(int r, int c){
        this.r = r;
        this.c = c;
    }
}