Kotlin 코테) 무인도 여행

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

문제 설명

문제 해석

1. maps는 Array<String> 이며 각 문자열에는 1~9와 X가 들어갈 수 있다.
2. X는 바다, 숫자 n은 그 지역에 있는 음식의 양을 나타내며 n일을 버틸 수 있다.
3. 상하좌우로 근접한 지역은 이동할 수 있는 육지이며 섬을 이룬다.

-> 각 섬에서 최대 며칠씩 머무를 수 있는지를 return

Input)
  maps: Array<String>
Output)
 answer: IntArray

알고리즘

1. 한 섬을 완전 탐색 -> dfs
   1) 지역에 번호를 매긴다. -> lastNum (즉, 섬 번호)
   2) 지역 방문 시 방문했음을 저장해야 함. -> boolean 값 이용
    -> numMap: Array<Array<Pair<Int, Boolean>>>
   3) 재탐색을 방지하기 위해 (섬번호 to 식량) 값을 저장 -> numToCount: MutableMap<Int, Int>
   4) 해당 지역에 있는 식량만큼 numToCount[섬번호]에 더함
   5) 근접해 있는 지역에 dfs 호출
   (but, 그 전 지역에 또 다시 넘겨주지 않기 위해 dfs에 from 파라피터 추가)
2. maps[0][0]에서 시작하여 이중for문 이용하여 모든 지역을 확인한다.
   1) 해당지역이 바다라면(즉, 해당지역 == 'X'면) 넘긴다.
   2) 해당지역 방문 유무가 false면 lastNum++ 후 dfs 함수를 호출
   3) numToCount의 값을 오름차순으로 정리 후 return

전체 흐름 코드 (dfs 생략)

fun solution(maps: Array<String>): IntArray {
	val height = maps.size
    val width = maps[0].length
    //1-2
    val numMap = Array(height) { Array<Pair<Int, Boolean>>(width) { Pair(0, false) } }
    //1-3
    val numToCount = mutableMapOf<Int, Int>()
    var lastNum = 0
        
    //from:
    //1:왼쪽, 2:위, 3:오른쪽, 4:아래쪽
    /**dfs(row: Int, column: Int, from: Int) 생략**/

    for(r in 0 until height) {
        for(c in 0 until width) {
            if(!numMap[r][c].second && numMap[r][c].first == 0 && maps[r][c] != 'X') {
                lastNum++
                dfs(r,c, 5)
            }
        }
     }
        
     if(lastNum == 0) return intArrayOf(-1)

     val answer = IntArray(lastNum) { 0 }
     //2-3
     val sorted = numToCount.toList().sortedBy { it.second }
     for(i in 0 until lastNum) {
         answer[i] = sorted[i].second
     }

     return answer
}

dfs 코드

//from
//왼쪽: 1, 위: 2, 오른쪽: 3, 아래: 4
fun dfs(row: Int, column: Int, from: Int) {
    val pair = numMap[row][column]
    //2-2
    if(pair.first == -1 || pair.first != 0) return

    val ele = maps[row][column]
    when(ele) {
    	//2-1
        'X' -> {
           numMap[row][column] = Pair(-1, true)
           return
        }
        else -> {
            numMap[row][column] = Pair(lastNum, true)
            numToCount[lastNum] = numToCount.getOrPut(lastNum) {0} + ele.digitToInt()
            if(from != 1 && column != 0) {
                dfs(row, column-1, 3)
            }
            if(from != 2 && row != 0) {
                dfs(row-1, column, 4)
            }
            if(from != 3 && column != width-1) {
                dfs(row, column+1, 1)
            }
            if(from != 4 && row != height-1) {
                dfs(row+1, column, 2)
            }     
        }
    }
}

작성하다 보니 바다 지역 번호 값(pair.first)을 -1로 굳이 안해도 될것 같다.