[백준 4963번] [Kotlin] 섬의 개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

난이도 : 실버 2
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

다른 DFS/BFS 탐색과 비슷하지만, 대각선 탐색이 가능한 8방향 탐색입니다.

따라서 (1,0) (0,1) (-1,0) (0,-1) 상하좌우 방향에 이어 (1,1) (1,-1) (-1,1) (-1,-1) 대각선 4방향, 총 8개 방향입니다.

 

 

소스코드

import java.util.*

val dx = arrayOf(0, 0, 1, -1, 1, -1, 1, -1)
val dy = arrayOf(1, -1, 0, 0, 1, -1, -1, 1)

var cnt = 0
var n = 0
var m = 0

lateinit var map: Array<Array<Int>>
lateinit var visited: Array<Array<Boolean>>

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()

    while (true) {
        cnt = 0

        val nm = readLine().split(" ").map { it.toInt() }
        n = nm[1]
        m = nm[0]

        if (n == 0 && m == 0) break

        map = Array(n) { Array(m) { 0 } }
        visited = Array(n) { Array(m) { false } }

        repeat(n) { x ->
            val st = StringTokenizer(readLine())
            repeat(m) { y ->
                map[x][y] = st.nextToken().toInt()
            }
        }

        repeat(n) { x ->
            repeat(m) { y ->
                if (map[x][y] == 1 && !visited[x][y]) {
                    dfs(x, y)
                    cnt++
                }
            }
        }

        sb.append("$cnt\n")
    }

    print(sb)
}


fun dfs(x: Int, y: Int) {
    visited[x][y] = true

    for (i in 0 until 8) {
        val nx = dx[i] + x
        val ny = dy[i] + y

        if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] || map[nx][ny] == 0) continue

        visited[nx][ny] = true
        dfs(nx, ny)
    }
}

 

코드 분석

1. dx, dy 방향 생성
2. 0, 0 이 입력될때까지 무한반복 시작
3. 섬이 있는 지역(==1)이면서, 방문하지 않은 지역일 경우 dfs 탐색 시작
   1. 방문한 지역에 방문처리
   2. 0~7 dx, dy를 탐색하며 재귀적으로 dfs 탐색 시행
4. 카운트 한 개수 출력

 

 

후기

전형적인 dfs/bfs 지만 8방향 이라는 점이 신선했던 문제입니다.