leetcode: 463. Island Perimeter

문제링크

풀이1

• BFS

class Solution {
    fun islandPerimeter(grid: Array<IntArray>): Int {
        val dx = listOf(1, 0, -1, 0)
        val dy = listOf(0, 1, 0, -1)    
        val row = grid.size
        val col = grid[0].size
        val visited = Array(row) { BooleanArray(col) { false } }
        var perimeter = 0
        val queue = LinkedList<Pair<Int, Int>>()
        outer@for (i in 0 until row) {        
            for (j in 0 until col) {
                if (grid[i][j] == 1) {
                    queue.add(Pair(i, j))
                    visited[i][j] = true
                    break@outer
                }
            }
        }
         
        while (queue.isNotEmpty()) {
            val (x, y) = queue.poll()
            
            for (i in 0..3) {
                val nx = x + dx[i]
                val ny = y + dy[i]
                if ((nx !in 0 until row) || (ny !in 0 until col)) {
                    perimeter++
                    continue
                }
                if (grid[nx][ny] != 1) {
                    perimeter++
                    continue
                }
                if (!visited[nx][ny]) {
                    queue.add(Pair(nx, ny))
                    visited[nx][ny] = true
                }
            }
        }
        return perimeter
    }
}

풀이2

• Math
• 전체 perimeter는 island * 4
• 겹치는 perimeter를 제거하기 위해서 island의 오른쪽, 아래에 island 존재 여부 확인
• 왼쪽, 위는 굳이 안해도 repeat * 2를 통해 해결 가능

class Solution {
    fun islandPerimeter(grid: Array<IntArray>): Int {
        var island = 0
        var repeat = 0
        val row = grid.size
        val col = grid[0].size
        
        for (i in 0 until row) {
            for (j in 0 until col) {
                if (grid[i][j] == 1) {
                    island++
                    if (i + 1 < row && grid[i + 1][j] == 1) repeat++ // right
                    if (j + 1 < col && grid[i][j + 1] == 1) repeat++ // bottom
                }
            }
        }
        return island * 4 - repeat * 2
    }
}