[프로그래머스][Kotlin] 리코쳇 로봇

해당 문제는 bfs를 응용하여 풀 수 있습니다.

일반적인 bfs와 다른 점은 상하좌우 중 막힐 때까지 해당 방향으로 계속 가야한다는 점입니다.

그렇기에 진행하면서 사람마다 다르겠지만 visit 배열에 false를 할 경우 정확한 결과가 안나올거 같다고 생각이 들어

쭉 진행하면서 진행하면 안되는 부근에 도착했을 경우 전 지점을 history라는 배열을 만들어 한번 미끄러져서 쭉 갔던 곳은 다시금 진행하지 않도록 작성하였습니다.

 

하기는 제가 작성한 코드와 실행 결과 입니다.

import java.util.ArrayDeque

class Solution {
    fun solution(board: Array<String>): Int {
        var answer: Int = Int.MAX_VALUE
        var ar = intArrayOf(0,0,1,-1)
        var ac = intArrayOf(1,-1,0,0)
        var visit = ArrayList<BooleanArray>()
        var count = ArrayList<IntArray>()
        var start = Info(0,0)
        var end = Info(0,0)

        for(i in 0 .. board.size-1){
            var tempvi = BooleanArray(board[i].length){true}
            var tempcn = IntArray(board[i].length){Int.MAX_VALUE}
            for(j in 0 .. board[i].length-1){
                if(board[i][j] == 'R'){
                    start = Info(i,j)
                    tempcn[j] = 0
                }
                if(board[i][j] == 'G'){
                    end = Info(i,j)
                }
                if(board[i][j] == 'D'){
                    tempvi[j] = false
                }
            }
            visit.add(tempvi)
            count.add(tempcn)
        }

        var history = ArrayList<Info>()

        var dq = ArrayDeque<Info>()
        dq.add(start)

        while(!dq.isEmpty()){
            val now = dq.pollFirst()
            val row = now.row
            val col = now.col
            if(now.equals(end)){
                answer = Math.min(answer,count[row][col])
            }
            for(i in 0 .. 3){
                var nr = row
                var nc = col
                while(true){
                    nr += ar[i]
                    nc += ac[i]
                    if(nr < 0 || nc < 0 || nr >= board.size || nc >= board[0].length) break
                    if(board[nr][nc] == 'D') break
                }
                nr -= ar[i]
                nc -= ac[i]
                if(history.contains(Info(nr,nc))) continue
                dq.addLast(Info(nr,nc))
                history.add(Info(nr,nc))
                count[nr][nc] = Math.min(count[row][col]+1, count[nr][nc])
            }
        }
        if(answer == Int.MAX_VALUE) answer = -1
        return answer
    }

    data class Info(
        val row: Int,
        val col: Int
    )
}

테스트 1 〉	통과 (20.93ms, 59.9MB)
테스트 2 〉	통과 (29.73ms, 60.6MB)
테스트 3 〉	통과 (1.47ms, 62.2MB)
테스트 4 〉	통과 (3.61ms, 61.9MB)
테스트 5 〉	통과 (7.59ms, 59.8MB)
테스트 6 〉	통과 (1.27ms, 60.1MB)
테스트 7 〉	통과 (20.09ms, 60.4MB)
테스트 8 〉	통과 (4.48ms, 61.2MB)
테스트 9 〉	통과 (9.82ms, 61.1MB)
테스트 10 〉	통과 (10.67ms, 59.8MB)
테스트 11 〉	통과 (0.54ms, 58.6MB)
테스트 12 〉	통과 (0.37ms, 62.2MB)
테스트 13 〉	통과 (1.22ms, 61.6MB)
테스트 14 〉	통과 (11.81ms, 59.6MB)
테스트 15 〉	통과 (3.71ms, 60.9MB)
테스트 16 〉	통과 (10.90ms, 60.1MB)
테스트 17 〉	통과 (3.03ms, 60.9MB)
테스트 18 〉	통과 (3.84ms, 59.9MB)
테스트 19 〉	통과 (6.99ms, 59.5MB)
테스트 20 〉	통과 (1.11ms, 62.4MB)
테스트 21 〉	통과 (13.65ms, 59.1MB)
테스트 22 〉	통과 (2.89ms, 60.4MB)
테스트 23 〉	통과 (1.20ms, 60.8MB)
테스트 24 〉	통과 (16.54ms, 60.3MB)
테스트 25 〉	통과 (10.64ms, 59.7MB)
테스트 26 〉	통과 (8.32ms, 59.3MB)
테스트 27 〉	통과 (2.66ms, 60.6MB)