Surrounded Regions - LeetCode

Problem

1. input: ‘X’와 ‘O’로 채워진 이차 행렬 board

2. output: board에서 X로 둘러싸이지 않은 O만 남긴 후 리턴

   

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.

Idea

X로 둘러싸인 O(연결된 무리)는 전부 X로 바뀐다.

즉, O가 X로 바뀌지 않으려면 board의 경계(가장 바깥쪽)에 O(연결된 무리중 적어도 하나)가 위치해야 한다.

이 성질을 활용하여, board의 경계 칸들을 탐색하여 O를 찾은 후, 해당 O를 시작으로 BFS하여 연결된 O를 찾아준다. 이 후, 앞서 찾은 O 무리들을 제외하고 모두 X로 바꿔주면 된다.

Solution

1. BFS

   board의 경계를 포함하는 O 무리 찾기

   이 외의 O는 전부 X로 변경

   import java.util.*
   
   class Solution {
       fun solve(board: Array<CharArray>): Unit {
           val moves = listOf(listOf(1, 0), listOf(-1,0), listOf(0,1), listOf(0,-1))
           // // 경계 좌표로부터 연속된 O 찾기
           val visited = Array<Array<Boolean>>(board.size){Array<Boolean>(board[0].size){false}}
           val group = mutableListOf<List<Int>>() //포위되지 않은 O 그룹 좌표 저장
           for (i in board.indices) {
               for (j in board[0].indices) {
                   if (i != 0 && i != board.size -1 && j != 0 && j!= board[0].size - 1) continue
                   if (!visited[i][j] && board[i][j] == 'O') {
                       val queue = LinkedList<List<Int>>()
                       queue.offerLast(listOf(i, j))
                       group.add(listOf(i, j))
                       visited[i][j] = true
                       while (queue.size > 0) {
                           val start = queue.pollFirst()
                           for (move in moves) { // 상,하,좌,우 확인
                               val x = start[0] + move[0]
                               val y = start[1] + move[1]
                               if (x in 0 until board.size && y in 0 until board[0].size && !visited[x][y] && board[x][y] == 'O') {
                                   queue.offerLast(listOf(x, y))
                                   group.add(listOf(x, y))
                                   visited[x][y] = true
                               }
                           }
                       }
                   }
               }
           }
           // 모든 좌표 X로 리셋
           for (i in board.indices) {
               for (j in board[0].indices) {
                   board[i][j] = 'X'
               }
           }
           group.forEach { board[it[0]][it[1]] = 'O' } // 저장한 좌표의 값 O로 변경
       }
   }
   

   시간 복잡도: 배열 탐색(경계를 포함하는 O 그룹 찾기) + 배열 탐색(X로 변경) + 배열 탐색(O로 변경) = n^2

   

Point