[Kotlin] 99 클럽 코딩 테스트 스터디 미들러 32일차 - 무인도 여행 (DFS)

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

[문제]

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1 크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠 동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러 갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

 

[제한 사항]

 

[입출력 예]

 

[풀이]

무인도의 지도를 파트 별로 나누어 최대 며칠 동안 각각 머무를 수 있는 DFS로 구하는 문제입니다.

아파트의 동 개수 구하기 등 유사한 문제를 몇 번 봤는데.. 볼 때 마다 어렵네요.

먼저 방문 체크를 위한 visited 배열과 지도에 방향의 움직을 기록할 directions 배열을 선언했습니다.

directions 같은 경우에는 x, y 좌표 기반이어야하기 때문에 Pair를 통해 구성했습니다.

 

• (0, 1): 오른쪽으로 이동
• (1, 0): 아래로 이동
• (0, -1): 왼쪽으로 이동
• (-1, 0): 위로 이동

여기서 주의할 점은 x, y  2차원 체크가 이루어져야하므로 visited도 2차원 배열이어야겠습니다.

문제 풀이에 사용될 중심 DFS 함수를 정의합니다.

fun dfs(x: Int, y: Int): Int {
    visited[x][y] = true
    var food = maps[x][y] - '0' // 현재 위치의 식량 값
    for (dir in directions) {
        val nx = x + dir.first
        val ny = y + dir.second
        if (nx in 0 until n && ny in 0 until m && !visited[nx][ny] && maps[nx][ny] != 'X') {
            food += dfs(nx, ny)
        }
    }
    return food
}

 

해당 문제에서는 이미 방문한 곳인지를 전체 Map 기준에서 DFS 함수를 호출하기 이전에 체크할 것입니다.

일단 DFS 함수 로직으로 진입했다면 true 처리를 해주었습니다.

식량 값을 정수형으로 변환해서 상하좌우 네 방향에 대한 위치 계산을 진행합니다.

nx는 다음 X 방향, ny는 다음 Y 방향을 가리킵니다. 
그리고 해당 방향이 아직 방문 하지 않았거나 방문이 가능한 지역이면 다시 DFS 함수를 호출하고 지역 변수로 선언되어 있는 food에 그 결과 값을 축적시켜줘야 합니다.
이러면 밀집되어 있는 한 지역에 대한 식량 값을 구하고, 다시 방문한 지역 또는 X 표시를 마주할 때 무인도 체크를 종료할 수 있습니다.

for (i in 0 until n) {
    for (j in 0 until m) {
        if (!visited[i][j] && maps[i][j] != 'X') {
            result.add(dfs(i, j))
        }
    }
}

 

각 지역별로 구한 food 값들을 결과 result에 추가해 줍니다.

2차원 배열 0, 0부터 시작하고 앞서 말씀드린 대로 방문 여부와 방문 가능 여부를 체크하여 호출합니다.

 

마지막에는 문제에 나온 조건대로 리스트가 비어있으면 -1, 아니라면 오름차순으로 정렬하여 반환합니다.

return if (result.isEmpty()) listOf(-1) else result.sorted()

 

전체 코틀린 코드입니다.

class Solution {
    fun solution(maps: Array<String>): List<Int> {
        val n = maps.size
        val m = maps[0].length
        val visited = Array(n) { BooleanArray(m) { false } }
        val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
        val result = mutableListOf<Int>()

        fun dfs(x: Int, y: Int): Int {
            visited[x][y] = true
            var food = maps[x][y] - '0'
            for (dir in directions) {
                val nx = x + dir.first
                val ny = y + dir.second
                if (nx in 0 until n && ny in 0 until m && !visited[nx][ny] && maps[nx][ny] != 'X') {
                    food += dfs(nx, ny)
                }
            }
            return food
        }

        for (i in 0 until n) {
            for (j in 0 until m) {
                if (!visited[i][j] && maps[i][j] != 'X') {
                    // 새로운 무인도를 발견하면 DFS 시작
                    result.add(dfs(i, j))
                }
            }
        }

        return if (result.isEmpty()) listOf(-1) else result.sorted()
    }
}