[프로그래머스] 리코쳇 로봇 LV.2 with Kotlin

문제

주어진 2차원 배열에서 R의 위치에 있는 로봇에 G까지 도달하는데 걸리는 최소 횟수 구하기

 

조건

1. 로봇은 상하좌우만 움직일 수 있다.

2. D는 벽

3. 막히는 구간까지 미끄러지듯 쭉 가야함

4. 목적지에 도달할 수 없다면 -1 반환

 

...D..R
.D.G...
....D.D
D....D.
..D....

 

 

풀이 과정

1. 이동했던 방향으로 다시 돌아가지 않도록 하기

2. 방문 했던 좌표는 pass

 

첫번째 시도 (DFS)

이동하는 모든 곳을 확인

테스트는 통과했지만 모든 경우의 수를 확인하는 방법으로 시간 초과

class Solution {
    val dx = arrayOf(1, -1, 0, 0)
    val dy = arrayOf(0, 0, -1, 1)
    var answer: Int = 0
    
    fun move(board: Array<String>, start: Array<Int>, temp: Array<Pair<Int, Int>>, count: Int, back: Int){
        // 방문한 위치라면
        if(temp.contains(Pair(start[0], start[1]))) return
        
        //최소 거리보다 길다면
        if(answer != 0 && count >= answer) return
        
        //골 이라면
        if(board[start[0]][start[1]] == 'G') {
            answer = if(answer == 0) count else Math.min(answer, count)
            return
        }
        // 방문한 적이 없다면 추가
        val now_temp = temp.copyOf()
        now_temp[count] = Pair(start[0], start[1])
        
        // 방향 이동
        for(i in 0..3){
            when(back){
                0 -> if(i == 1) continue
                1 -> if(i == 0) continue
                2 -> if(i == 3) continue
                3 -> if(i == 2) continue
            }
            
            var now = start.copyOf()
            while(true){
                if(now[0]+dx[i] < 0 || now[0]+dx[i] >= board.size 
                   || now[1]+dy[i] < 0 || now[1]+dy[i] > board[0].length-1) break
                
                if(board[now[0]+dx[i]][now[1]+dy[i]] == 'D') break
                
                now[0] += dx[i]
                now[1] += dy[i]
            }
            
            move(board, now, now_temp, count+1, i)
        }
    }
    
    fun solution(board: Array<String>): Int {
        var R = arrayOf(-1, -1)
    
        //R의 위치 찾기
        for(i in board.indices){
            val index = board[i].indexOf('R')
            if(index != -1){
                R[0] = i
                R[1] = index
                break
            }
        }
        
        move(board, R, Array<Pair<Int,Int>>(board.size * board[0].length, {Pair(-1, -1)}), 0, -1)
        
        if(answer == 0) return -1
        return answer
    }
}

 

두번째 시도 (BFS)

BFS는 DFS와는 다르게 G을 찾으면 바로 종료

 

import java.util.*

class Solution {
    fun solution(board: Array<String>): Int {
        var answer: Int = 0
        val dx = arrayOf(1, -1, 0, 0)
        val dy = arrayOf(0, 0, -1, 1)
    
    
        val q : Queue<Pair<Int, Int>> = LinkedList<Pair<Int, Int>>()    
        //R의 위치 찾기
        for(i in board.indices){
            val index = board[i].indexOf('R')
            if(index != -1){
                q.add(Pair(i, index))
                break
            }
        }
        
        // 1. 왔던 방향
        val history : Queue<Int> = LinkedList<Int>()
        history.add(-1)
        // 2. count
        val count : Queue<Int> = LinkedList<Int>()
        count.add(0)
        
        // 3. 와봤던 좌표
        val h_location = ArrayList<Pair<Int, Int>>()
        
        while(!q.isEmpty()){
            val start = q.poll()
            val c = count.poll()
            val h = history.poll()
            
            //방문했던 좌표라면 pass 아니면 저장 후 진행
            if(h_location.contains(start)) continue
            else h_location.add(start)
            
            // 현재 위치가 G이라면
            if(board[start.first][start.second] == 'G') {
                answer = c
                break
            }

            // 이동
            for(i in 0..3){
                if(i == h) continue
                
                var nx = start.first
                var ny = start.second
                
                // 막힐 때까지 진행
                while(true){
                    if(nx + dx[i] < 0 || nx + dx[i] >= board.size ||
                            ny + dy[i] < 0 || ny + dy[i] >= board[0].length) break
                    if(board[nx+dx[i]][ny+dy[i]] == 'D') break
                    
                    nx += dx[i]
                    ny += dy[i]
                }
                
                if(Pair(nx, ny) == start) continue
                q.add(Pair(nx, ny))
                count.add(c+1)
                
                // 왔던 방향
                when(i){
                    0 -> history.add(1)
                    1 -> history.add(0)
                    2 -> history.add(3)
                    3 -> history.add(2)
                }
            }
        }
        
        if(answer == 0) return -1
        return answer
    }
}