Surrounded Regions - BFS 알고리즘

Surrounded Regions - LeetCode

문제 설명

X로 사방이 둘러쌓인 O들을 X로 뒤집어라

맨 아래줄에 O는 한쪽이 X로 막혀있지 않기 때문에 뒤집지 않는다.

---

문제 해결 방안

1. 모든 칸을 하나씩 탐색한다.

1-1. X이거나 탐색한 적 있으면 패스한다.

1-2. O이면 2단계로 넘어간다.

 

2. BFS 알고리즘을 통해 상하좌우의 칸을 탐색한다.

2-1. 보드를 넘어가거나, X를 만나면 탐색을 멈춘다.

2-2. 탐색한 모든 O를 마스킹한다.

2-3. 탐색할 수 있는 모든 영역을 탐색했다면 3단계로 넘어간다

 

3. 마스킹한 칸들을 뒤집는다.

3-1. 단, 2단계에서 탐색중에 보드를 넘어갔다면 뒤집지 않는다.

3-2. 1단계로 돌아가 반복한다.

---

코드 (TypeScript)

function solve(board: string[][]): void {
    let maxRow = board.length;
    let maxColumn = board[0].length;
    
    // init mask
    let mask = [];
    
    for (let i = 0; i < maxRow; i++) {
        let list = [];
        
        for (let j = 0; j < maxColumn; j++) {
            list.push();
        }
        
        mask.push(list);
    }
    
    // BFS
    for (let i = 0; i < maxRow; i++) {
        for (let j = 0; j < maxColumn; j++) {
            if (board[i][j] === 'X' || mask[i][j] === 1) {
                continue;
            }
            
            let queue = [[i, j]];
            // connedted 'O' region
            let region = [];
            let surrounded = true;

            while (queue.length > 0) {
                const [r, c] = queue.shift();

                // meet border = not surrounded
                if (r < 0 || r >= maxRow || c < 0 || c >= maxColumn) {
                    surrounded = false;
                    continue;
                } else if (mask[r][c] === 1 || board[r][c] === 'X') {
                    continue;
                }

                mask[r][c] = 1;
                region.push([r, c]);

				// 4-way search
                queue.push([r + 1, c]);
                queue.push([r - 1, c]);
                queue.push([r, c + 1]);
                queue.push([r, c - 1]);
            }
            
            // if surrounded, flip the board
            if (surrounded) {
                for (let [r, c] of region) {
                    board[r][c] = 'X';
                }
            }
        }
    }
};