[백준 4993번] [Kotlin] Red and Black

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

4993번: Red and Black

 

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

 

 

설명

전형적인 DFS/BFS로 도달 가능한 위치 확인하기 문제입니다.

시작점(@)에서 DFS/BFS를 시작하여, #로 막혀 갈 수 없는 곳을 제외하고,

갈 수 있는 곳을 카운팅하는 문제입니다.

 

해당 문제에서는 DFS/BFS 중 어느 것을 사용해도 무관하며,

저는 DFS를 사용하였습니다.

 

 

 

소스코드

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

lateinit var visited: Array<BooleanArray>
lateinit var map: Array<CharArray>
val dx = intArrayOf(0, 0, 1, -1)
val dy = intArrayOf(1, -1, 0, 0)
var cnt = 0
var n = 0
var m = 0

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

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

        var start = Node(0, 0)

        map = Array(n) { x ->
            val line = readLine().toCharArray()
            for (y in line.indices) if (line[y] == '@') start = Node(x, y)
            line
        }
        visited = Array(n) { BooleanArray(m) }

        cnt = 1
        visited[start.x][start.y] = true

        dfs(start.x, start.y)
        sb.append(cnt).append("\n")
    }

    print(sb)
}

fun dfs(x: Int, y: Int) {
    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until n || ny !in 0 until m || visited[nx][ny] || map[nx][ny] == '#') continue
        visited[nx][ny] = true
        cnt++
        dfs(nx, ny)
    }
}

 

저 같은 경우, cnt, map, visited를 전역 변수로 두고,

dfs를 재귀 형태로 구현하여 탐색을 하였습니다.

 

한 칸에서 상하좌우 인접한 칸을 대상으로,

방문하지 않았으면서(visited[nx][ny] == false), #가 아니라면(map[nx][ny] != '#')

해당 칸을 탐색합니다.

 

 

 

후기

기분전환 삼아 DFS/BFS 문제가 풀고 싶어졌는데,

쉬운 문제들은 이미 거의 다 푼 탓에 영어 문제까지 풀게 되었습니다...