[leetcode] 417. Pacific Atlantic Water Flow

from island to ocean

• 단점 : 모든 island 의 (x, y) 좌표를 BFS 순회

data class Ocean(var pacific: Boolean, var atlantic: Boolean)

data class Position(val x: Int, val y: Int)

class Solution {
    val dx = listOf(1, 0, -1, 0)
    val dy = listOf(0, 1, 0, -1)
    
    fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
        val m = heights.size
        val n = heights[0].size // n >= 1
        
        val result = mutableListOf<List<Int>>()
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (bfs(heights, i, j)) {
                    result.add(listOf(i, j))
                }
            }
        }
        
        return result
    }
    
    fun bfs(heights: Array<IntArray>, i: Int, j: Int): Boolean {
        val m = heights.size
        val n = heights[0].size // n >= 1
        
        val queue: Queue<Position> = LinkedList()
        val visited = Array(m) { BooleanArray(n) { false } }
        queue.add(Position(j, i))
        visited[i][j] = true
        
        val ocean = Ocean(false, false)
        
        while (queue.isNotEmpty()) {
            val position = queue.poll()
            
            if (position.x == 0 || position.y == 0) ocean.pacific = true
            if (position.x == n - 1 || position.y == m - 1) ocean.atlantic = true
            
            for (k in 0 until 4) {
                val nx = position.x + dx[k]
                val ny = position.y + dy[k]
                
                if (nx !in 0 until n || ny !in 0 until m) continue
                if (visited[ny][nx]) continue
                if (heights[ny][nx] > heights[position.y][position.x]) continue
                
                visited[ny][nx] = true
                queue.add(Position(nx, ny))                
            }
        }
        
        return ocean.pacific && ocean.atlantic
    }
}

from ocean to island

• 장점 : 필요한 (x, y) 좌표에 대해서 BFS 순회

data class Position(val x: Int, val y: Int)

class Solution {
    val dx = listOf(1, 0, -1, 0)
    val dy = listOf(0, 1, 0, -1)
    
    fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
        val m = heights.size
        val n = heights[0].size // n >= 1
        
        val pQueue: Queue<Position> = LinkedList()
        val aQueue: Queue<Position> = LinkedList()
        val pVisited = Array(m) { BooleanArray(n) { false } }
        val aVisited = Array(m) { BooleanArray(n) { false } }
        
        for (i in 0 until m) {
            pQueue.add(Position(0, i))
            aQueue.add(Position(n - 1, i))
            pVisited[i][0] = true
            aVisited[i][n - 1] = true
        }
        
        for (j in 0 until n) {
            pQueue.add(Position(j, 0))
            aQueue.add(Position(j, m - 1))
            pVisited[0][j] = true
            aVisited[m - 1][j] = true
        }
        
        bfs(heights, pQueue, pVisited)
        bfs(heights, aQueue, aVisited)
        
        val result = mutableListOf<List<Int>>()
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (pVisited[i][j] && aVisited[i][j]) result.add(listOf(i, j))
            }
        }
        return result
    }
    
    fun bfs(heights: Array<IntArray>, queue: Queue<Position>, visited: Array<BooleanArray>) {
        val m = heights.size
        val n = heights[0].size // n >= 1
        
        while (queue.isNotEmpty()) {
            val position = queue.poll()
            
            for (k in 0 until 4) {
                val nx = position.x + dx[k]
                val ny = position.y + dy[k]
                
                if (nx !in 0 until n || ny !in 0 until m) continue
                if (visited[ny][nx]) continue
                if (heights[position.y][position.x] > heights[ny][nx]) continue
                
                visited[ny][nx] = true
                queue.add(Position(nx, ny))            
            }
        }
    }
}