문제

https://leetcode.com/problems/number-of-islands/

문제 해석

간단한 DFS문제이다. (BFS로도 가능하다)
1이면 땅이고, 0이면 물이기 때문에 상하좌우를 탐색해서 1인 녀석들이 존재하지 않을 때까지 반복하고, 한 그룹이 끝났다면 +1을 해준다.
이런 식으로 반복해서 총 몇개의 그룹이 존재하는지 찾는 문제이다.

문제 풀이

나의 경우 처음으로 생각난게 BFS였다.(아직 부족해서 DFS가 바로 떠오르지 않나 보다..)
문제를 보자마자 이차원 배열 내에서 1을 찾는 순간 주변에 몇개가 있는지를 파악하고 전부 0이 된다면 +1 을 한다가 먼저 생각난거 같다.
생각을 조금만 전환한다면, 시작지점을 찾았다면, 상하좌우로 다시한번 너비로 탐색을 한다면 굳이 Queue를 사용하지 않고도 보다 깔끔하게 코드를 작성할 수 있다.

코드

<BFS>
class Solution {
    // 왼, 상단, 오른쪽, 하단
    private val nx = listOf(-1, 0, 1, 0)
    private val ny = listOf(0, 1, 0, -1)

    fun numIslands(grid: Array<CharArray>): Int {
        var cnt = 0
        // 방문 했는지에 대한 ARRAY가 있으면 좋은게 아니라 필요해 싯팔
        val visited = Array(grid.size) {
            BooleanArray(grid[0].size) { false }
        }

        val queue: Queue<Pair<Int, Int>> = LinkedList<Pair<Int, Int>>()
        for (i in 0 until grid.size) {
            for (j in 0 until grid[i].size) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    queue.add(Pair(i, j))
                    visited[i][j] = true

                    while (queue.isNotEmpty()) {
                        val pos = queue.poll()

                        for (k in 0 until 4) {
                            if ((pos.first + nx[k] < 0 || pos.first + nx[k] >= grid.size) || (pos.second + ny[k] < 0 || pos.second + ny[k] >= grid[0].size)){
                                continue
                            }
                            else {
                                if (grid[pos.first + nx[k]][pos.second + ny[k]] == '1' && !visited[pos.first + nx[k]][pos.second + ny[k]]) {
                                    queue.add(Pair(pos.first + nx[k], pos.second + ny[k]))
                                    visited[pos.first + nx[k]][pos.second + ny[k]] = true
                                }
                            }
                        }
                    }
                    cnt++
                }
            }
        }
        return cnt
    }
}

<DFS>
class Solution2 {
    fun numIsland(grid: Array<CharArray>): Int {
        if (grid.size == 0) return 0
        var result: Int = 0

        grid.forEachIndexed { i, it ->
            it.forEachIndexed { j, value ->
                if (grid[i][j] == '1') {
                    result += dfs(grid,i,j)
                }
            }
        }
        return result
    }

    fun dfs(grid: Array<CharArray>, i: Int, j: Int): Int {
        if (i < 0 || j < 0 || i >= grid.size || j >= grid[0].size || grid[i][j] == '0') {
            return 0
        }
        grid[i][j] = '0'
        dfs(grid,i + 1, j)
        dfs(grid, i - 1, j)
        dfs(grid, i, j - 1)
        dfs(grid, i, j + 1)
        return 1
    }
}