백준 - 섬의 개수(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/4963

 

[문제 설명]

그래프탐색하기.

[접근 방법]

DFS로 그래프를 탐색한 후에, 한 육지를 기준으로 이어진 육지를 전부 방문 처리.

처음엔 4방면인줄 알았는데 대각선으로도 탐색이 가능해서 방향 배열을 추가해줘야 했다.

BFS 카테고리로 푼 문제인데 깜빡하고 DFS로 풀었다. 

 

시간복잡도는 그래프를 전부 탐색해야하므로 맵 전체를 탐색 -> 가로*세로 -> O(W*H)

공간복잡도도 매번 맵 크기만한 배열을 만들어줘야 하므로 O(W*H)

import java.io.BufferedReader
import java.io.InputStreamReader

// 1은 땅 0은 바다
val dy = intArrayOf(-1,0,1,0,-1,1,1,-1)
val dx = intArrayOf(0,1,0,-1,1,1,-1,-1)
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    while (true) {
        val (w,h) = readLine().split(" ").map {it.toInt()}
        if (w == 0 || h == 0) {
            return
        }

        val map = Array(h){IntArray(w)}
        val isVisited = Array(h){BooleanArray(w)}
        repeat(h) {
            map[it] = readLine().split(" ").map { it.toInt() }.toIntArray()
        }

        var cntOfLand = 0
        for (idxOfRow in 0 until h) {
            for (idxOfColumn in 0 until w) {
                // 방문하지 않은 곳이고, 땅이면 dfs 시작.
                if (!isVisited[idxOfRow][idxOfColumn] && map[idxOfRow][idxOfColumn] == 1) {
                    checkLand(isVisited, map, idxOfRow, idxOfColumn)
                    cntOfLand++
                }
            }
        }

        println(cntOfLand)
    }
}

fun checkLand(visited: Array<BooleanArray>, map: Array<IntArray>, startDy: Int, startDx: Int) {
    // 현재 좌표가 맵 밖이거나, 이미 방문한 곳이거나, 바다(0)면 끝
    if (startDy !in map.indices || startDx !in map[0].indices || visited[startDy][startDx] || map[startDy][startDx] == 0) {
        return
    } else {
        // 다 만족하면 방문처리
        visited[startDy][startDx] = true
    }

    for (idxOfDire in dy.indices) {
        checkLand(visited, map, startDy+dy[idxOfDire], startDx+dx[idxOfDire])
    }
}