[TIL] BFS의 방문여부 체크 순서

Leetcode의 Regions Cut By Slashes를 풀며 TimeLimit이 걸렸다.

슬래쉬로 나뉜 영역의 개수를 체크하기 위해 flood fill이라는 기법을 사용했고 이 때 완전탐색을 하는 BFS를 사용했다.

문제가 된 코드는

    fun bfs(grid: Array<Array<Int>>, i: Int, j: Int) {
        val queue = LinkedList<Pair<Int, Int>>()
        queue.add(Pair(i, j))
        while(!queue.isEmpty()) {
            var node = queue.poll()
            val y = node.first
            val x = node.second
            grid[y][x] = 1

            if (checkValidNode(grid, y - 1, x)) queue.add(Pair(y - 1, x)) //상 
            if (checkValidNode(grid, y + 1, x)) queue.add(Pair(y + 1, x)) //하 
            if (checkValidNode(grid, y, x - 1)) queue.add(Pair(y, x - 1))//좌 
            if (checkValidNode(grid, y, x + 1)) queue.add(Pair(y, x + 1))//우            
        }
    }
    
    fun checkValidNode(grid: Array<Array<Int>>, i: Int, j: Int): Boolean {
        if (i < 0 || i >= grid.size) return false
        if (j < 0 || j >= grid.size) return false
        if (grid[i][j] == 1) return false

        return true
    }

이 부분이었다.

원인은 노드를 큐에 집어넣은 후 꺼낼 때 방문체크(fill)를 하다보니 이미 큐에 넣은 노드를 중복해서 넣게 된 것이었다.

    fun bfs(grid: Array<Array<Int>>, i: Int, j: Int) {
        val queue = LinkedList<Pair<Int, Int>>()
        queue.add(Pair(i, j))
        grid[i][j] = 1

        while(!queue.isEmpty()) {
            var node = queue.poll()
            val y = node.first
            val x = node.second

            if (isValidNode(grid, y - 1, x)) {
                queue.add(Pair(y - 1, x)) 
                grid[y - 1][x] = 1
            }
            if (isValidNode(grid, y + 1, x)) {
                queue.add(Pair(y + 1, x)) //하
                grid[y + 1][x] = 1
            } 
            if (isValidNode(grid, y, x - 1)) {
                queue.add(Pair(y, x - 1))//좌
                grid[y][x - 1] = 1
            } 
            if (isValidNode(grid, y, x + 1)) {
                queue.add(Pair(y, x + 1))//우
                grid[y][x + 1] = 1
            }            
        }
    }

위와 같이 큐에 넣을 때 방문체크를 하여 해결하였다.

방문체크 순서를 잘 고려해야 한다.