<프로그래머스> 무인도 여행(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%AC%B4%EC%9D%B8%EB%8F%84%20%EC%97%AC%ED%96%89

[프로그래머스]

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

 

문제를 딱 봤을 때 풀이방법이 번뜩 생각나는 경우에는 기분이 참 좋다~

예제 설명을 보자마자 내가 전에 자바로 열심히 푸는 연습을 했었던 DFS, BFS 문제들이 스쳐지나가더라

배열 2개 만들고 좌표 배열 만들고 알고리즘 돌리고... 그렇게 했는데도 기억이 흐릿했다.

코틀린으로 2차원 BFS는 이 문제가 처음인 거 같다.

 

이 문제는 전체좌표를 돌면서 BFS를 진행했다.

X가 아니고 이미 지나간 좌표가 아니라면 해당 좌표의 값을 더하는 식으로 코드를 짰다.

예외 조건일 때는 continue 시키고 아니면 큐에 넣는다.

가장 나한테 익숙한 BFS 포맷이다.

 

다 풀고나서 다른 사람들의 풀이를 보니까 DFS로 푼 사람들도 조금 있더라

내 코드에서 sum을 전역변수로 두고 재귀함수로 구조를 바꾸면 된다.

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    // 좌표 방향
    private val dy = listOf(0, 1, 0, -1)
    private val dx = listOf(1, 0, -1, 0)
    
    fun solution(maps: Array<String>): IntArray {
        var answer: IntArray = intArrayOf()
        val visited = Array<BooleanArray>(maps.size) { BooleanArray(maps[0].length) {false} }

        // 모든 좌표 탐색
        for (i in maps.indices) {
            for (j in maps[0].indices) {
                if (!visited[i][j] && maps[i][j] != 'X') {
                    answer += bfs(maps, visited, i, j)
                }
            }
        }

        return if (answer.isEmpty()) intArrayOf(-1) else answer.sortedArray()
    }
    
    private fun bfs(maps: Array<String>, visited: Array<BooleanArray>, row: Int, col: Int): Int {
        val q = ArrayDeque<Pair<Int, Int>>()
        q.add(Pair(row, col))
        visited[row][col] = true

        var sum = (maps[row][col] - '0')
        while (q.isNotEmpty()) {
            val cur = q.removeFirst()

            for (i in 0..3) {
                val nextRow = cur.first + dy[i]
                val nextCol = cur.second + dx[i]

                if (nextRow < 0 || nextRow >= maps.size || nextCol < 0 || nextCol >= maps[0].length) continue
                if (visited[nextRow][nextCol]) continue

                if (maps[nextRow][nextCol] != 'X') {
                    visited[nextRow][nextCol] = true
                    q.add(Pair(nextRow, nextCol))
                    sum += (maps[nextRow][nextCol] - '0')
                }
            }
        }

        return sum
    }
}