프로그래머스 블록 이동하기 Kotlin (bfs)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력 예

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

풀이

풀이 구상은 쉽지만 구현이 까다로운 문제이다.

bfs로 로봇을 이동, 회전시켜 목적지에 도달하는 시간을 구해야 하는, 알고리즘만 생각하면 간단한 문제이지만,

회전을 구현하는 게 까다롭다.

우선 로봇은 두 칸을 차지하기 때문에, 로봇의 한 칸을 기준으로 잡고 다른 한 칸이 뻗어있는 방향을 저장한다.

본인은 bfs의 큐에 로봇의 기준 좌표, 방향, 도달 시간을 저장하였다.

로봇이 이동하는 경우는

1. 상하좌우 이동

2. 로봇의 기준 좌표를 축으로 회전(시계,반시계)

3. 로봇의 나머지 좌표를 축으로 회전(시계,반시계)

위와 같은 경우들이 있고, 로봇의 두 좌표가 벽에 막혔는지, 로봇의 기준 좌표가 x방향일 때 이미 방문했는지, 그래프의 범위 바깥인지, 회전한 경우 회전하는 길에 벽이 있는지 등을 확인하며 탐색하면 된다.

 

로봇의 기준 좌표를 r,c라고 하고 방향을 dir, 로봇이 뻗어 있는 좌표 rr,cc라 할 때,

1번 과정(상하좌우 이동)은 visited[r][c][dir]에 아직 방문하지 않았는지 등의 조건을 확인하고 큐에 r,c,dir,time+1을 넣는다.

 

2번 과정(로봇 기준 좌표를 축으로 회전)은 기준이 되는 좌표는 이동하지 않기 때문에, visited[r][c][회전한dir] 등의 조건을 확인하고 큐에 r,c,회전한dir,time+1을 넣는다.

 

3번 과정(로봇의 나머지 좌표를 축으로 회전)은 기준이 되는 좌표가 회전하여 이동하였기 때문에 회전하여 이동한 좌표 를 nr,nc라 하면 visited[nr][nc][회전한dir의 반대방향] 등의 조건을 확인하고 큐에 nr,nc, 회전한dir의 반대방향, time+1을 넣는다.

 

로봇의 이동은 쉽게 구현할 수 있었지만, 회전은 구현하는 게 쉽지 않아 밥때도 놓치고 밥맛이 떨어져버렸다.

역시 카카오 문제다.

 

 

코드

import java.util.*
class Solution {
    
    data class Robot(val r1 : Int, val c1 : Int, val dir : Int, val time : Int)
    //상좌하우
    val move = arrayOf(intArrayOf(-1,0),intArrayOf(0,-1),intArrayOf(1,0),intArrayOf(0,1))
    val rotateR = arrayOf(-1,-1,1,1)
    val rotateC = arrayOf(1,-1,-1,1)
    fun isInside(r1 : Int, c1 : Int, r2 : Int, c2 : Int, size : Int):Boolean{
        if(r1>=0 && r1<size && c1>=0 && c1<size && r2>=0 && r2<size && c2>=0 && c2<size){
            return true
        }
        return false
    }
    fun isBlock(r : Int, c : Int,board : Array<IntArray>) : Boolean{
        if(board[r][c]==1)
            return true
        return false
    }
    
    fun bfs(board : Array<IntArray>): Int{
        val n = board.size
        val visited = Array<Array<BooleanArray>>(n){Array<BooleanArray>(n){BooleanArray(n)}}
        val q : Queue<Robot> = LinkedList<Robot>()
        q.add(Robot(0,0,3,0))
        visited[0][0][3]=true
        while(q.isNotEmpty()){
            val (r,c,dir,time) = q.poll()
            val rr = r+move[dir][0]
            val cc = c+move[dir][1]
            if((r==n-1 &&c==n-1)||(rr==n-1&&cc==n-1)){
                return time
            }
            //move
            for(i in move.indices){
                val nr = r+move[i][0]
                val nc = c+move[i][1]
                val nrr = rr+move[i][0]
                val ncc = cc+move[i][1]
                if(!isInside(nr,nc,nrr,ncc,n))continue
                if(isBlock(nr,nc,board)||isBlock(nrr,ncc,board))continue
                if(visited[nr][nc][dir])continue
                q.add(Robot(nr,nc,dir,time+1))
                visited[nr][nc][dir]=true
            }
            //rotate
            //rc축으로 회전
            var newDir= dir
            for(i in 3 downTo 2 ){
                newDir =(newDir+i)%4 
                //검사할 좌표
                val xr = rr+move[newDir][0]
                val xc = cc+move[newDir][1]
                //회전된 좌표
                val nrr = r+move[newDir][0]
                val ncc = c+move[newDir][1]
                // println("$newDir $xr $xc $nrr $ncc")
                if(!isInside(r,c,nrr,ncc,n))continue
                if(isBlock(xr,xc,board))continue
                if(visited[r][c][newDir]) continue
                if(isBlock(nrr,ncc,board))continue
                q.add(Robot(r,c,newDir,time+1))
                visited[r][c][newDir]=true
            }
            
            //rrcc축으로 회전
            newDir = (dir+2)%4
            for(i in 3 downTo 2){
                newDir =(newDir+i)%4
                //검사할 좌표
                val xr = r+move[newDir][0]
                val xc = c+move[newDir][1]
                //회전된 좌표
                val nr = rr+move[newDir][0]
                val nc = cc+move[newDir][1]
                if(!isInside(nr,nc,r,c,n))continue
                if(isBlock(xr,xc,board))continue
                if(visited[nr][nc][(newDir+2)%4])continue
                if(isBlock(nr,nc,board))continue
                q.add(Robot(nr,nc,(newDir+2)%4,time+1))
                visited[nr][nc][(newDir+2)%4]=true
            }
        }
        return 0
    }
    
    fun solution(board: Array<IntArray>): Int {
        
        return bfs(board)
    }

}