백준 1726 로봇 Kotlin (bfs) 2022-06-15 다익스트라 추가

문제 출처 : https://www.acmicpc.net/problem/1726

1726번: 로봇

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

bfs에 대한 이해도를 높여주는 좋은 문제이다!!

처음엔 어렵게 생각해서 다익스트라로 풀었고, 명령 1의 조건인 1,2,3칸이라는 것을 보지 못해서 맞왜틀을 계속 시전 하다가, 문제를 다시 읽어보고, 코드도 엎어서 다시 풀었다.

 

그래프 탐색에서 bfs의 큰 특징은 dfs와 다르게 도착지에 가장 먼저 도착하는 경로가 최단 경로가 된다는 것이다.

이 특징을 유지하면서 조건들을 추가한다는 컨셉으로 풀면, 어렵지 않다.

문제에선, 방향 전환이 적을수록 최단 경로를 찾는 데에 유리하다.

따라서 기존 칸에서 방향 전환 없이 기존 방향 그대로 1,2,3칸을 이동하는 Go 명령을 우선적으로 수행한 후,

기존 칸에서 나머지 3 방향으로 방향 전환한 후, 위의 과정을 반복한다.

 

그러면 bfs는

1. 기존 방향 먼저 1,2,3칸 방문

2. 나머지 3 방향 전환

3. 1에서 방문한 3 개의 칸들에 대해 다시 기존 방향 먼저 1,2,3칸 방문, 나머지 3방향 전환

 

크게 3단계로 동작할 것이다.

이렇게 만든 bfs는 도착지에 도달했을 때 최소 명령 횟수를 보장하게 된다.

 

2022-06-15

기존 풀이가 기억나지 않는 상태로 다시 풀었고, 이번엔 다익스트라로 통과했다.

bfs, 다익스트라 둘 다 풀리는 문제라면 사실 bfs로 푸는 게 정해라고 생각한다.

하지만 같은 문제에 대한 다양한 풀이를 적용하는 것은 좋은 공부인 것 같다.

bfs 풀이가 다익스트라 풀이보다 160ms정도 빠르다.

    while(pq.isNotEmpty()){
        val cur = pq.poll()
        for(i in 0 until 4){
            var nCnt = if(cur.d == i) cur.cnt else cur.cnt+1
            //두 번 돌려야 하는 경우
            if((cur.d+i)%4==1) nCnt++
            //end
            if(i==ed && cur.r == er && cur.c == ec) return nCnt
            if(visited[i][cur.r][cur.c]<nCnt) continue
            //go 1,2,3
            for(j in 1 .. 3){
                val nr = cur.r + dir[i][0]*j
                val nc = cur.c + dir[i][1]*j
                if(nr !in 0 until n || nc !in 0 until m) continue
                if(graph[nr][nc]=='1') break
                if(visited[i][nr][nc] <= nCnt+1) continue
                visited[i][nr][nc] = nCnt+1
                pq.add(Node(nr,nc,i,nCnt+1))
            }
        }
    }

위 코드가 핵심이다.

전 풀이와 다르게 좌표 이동없이 현재 칸에서 4방향에 대한 체크 먼저 하고, 유효한 경우(현재 좌표의 4가지 방향에 대해 들어있는 값보다 현재 탐색하는 값이 더 작거나 같을 때) go 1,2,3을 수행한다.

 

 

코드1(BFS)

import kotlin.math.*
import java.util.*
val INF = 987654321
val dirXY = arrayOf(arrayOf(0,1),arrayOf(0,-1),arrayOf(1,0),arrayOf(-1,0))
val br = System.`in`.bufferedReader()

data class Node(var r : Int , var c : Int, var dir : Int, var cnt : Int)

//몇 번 돌려야하는지 계산
fun calRotate(curDir : Int, nextDir : Int) : Int{
    return when{
        nextDir ==0 -> when{
            curDir>=2 -> 1
            curDir==1 -> 2
            else -> 0
        }
        nextDir ==1 -> when{
            curDir>=2 -> 1
            curDir==0 -> 2
            else -> 0
        }
        nextDir ==2 -> when{
            curDir<2 -> 1
            curDir==3 -> 2
            else -> 0
        }
        else -> when{
            curDir<2 -> 1
            curDir==2 ->2
            else -> 0
        }
    }
}

fun bfs(sr : Int, sc : Int, sdir : Int, er : Int, ec : Int, edir : Int, n : Int, m : Int, graph : Array<IntArray>, visited : Array<Array<BooleanArray>>) : Int{

    val q : Queue<Node> = LinkedList<Node>()
    q.add(Node(sr,sc,sdir,0))
    visited[sr][sc][sdir]=true
    var answer=INF
    
    while(q.isNotEmpty()){
        val cur =q.poll()
        //도착 지점에 가장 먼저 도착한 경우가 최단 명령 횟수
        //기존의 최단 거리를 찾는 bfs의 컨셉 유지
        //도착하면 방향 맞춰서 출력
        if(cur.r==er && cur.c==ec){
            return cur.cnt+ calRotate(cur.dir,edir)
        }
        
        var nr=cur.r
        var nc=cur.c
        //기존 방향 1,2,3칸 방문, +1씩
        for(i in 0 until 3){
            nr+=dirXY[cur.dir][0]
            nc+=dirXY[cur.dir][1]
            if(nr !in 0 until n || nc !in 0 until m) break //그래프 넘어간 경우 스탑
            if(visited[nr][nc][cur.dir] ) continue // 이미 방문한 칸은 스킵
            if(graph[nr][nc]==1) break //1만나면 스탑
            q.add(Node(nr,nc,cur.dir,cur.cnt+1))
            visited[nr][nc][cur.dir]=true
        }
        //현재 자리에서 방향만 전환한 후 큐에 추가
        for(dir in 0 until 4){
            if(dir==cur.dir) continue
            if(visited[cur.r][cur.c][dir] ) continue
            q.add(Node(cur.r,cur.c,dir,cur.cnt+ calRotate(cur.dir,dir)))
            visited[cur.r][cur.c][dir]=true
        }
    }
    return answer
}


fun main() = with(System.out.bufferedWriter()){

    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array(n){
        br.readLine().split(' ').map{it.toInt()}.toIntArray()
    }
    val (sr,sc,sdir) = br.readLine().split(' ').map{it.toInt()}
    val (er,ec,edir) = br.readLine().split(' ').map{it.toInt()}
    write("${bfs(sr-1,sc-1,sdir-1,er-1,ec-1,edir-1,n,m,graph,Array(n){Array(m){BooleanArray(4)} })}")

    close()
}

코드2(다익스트라)

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

data class Node(
    val r: Int,
    val c: Int,
    val d: Int,
    val cnt: Int
)
lateinit var visited: Array<Array<IntArray>>
lateinit var graph: Array<CharArray>
val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(0,-1),
    arrayOf(1,0),
    arrayOf(-1,0)
)

fun bfs(sr: Int, sc: Int, sd: Int, er: Int, ec: Int, ed: Int, n: Int, m: Int) : Int{
    val pq = PriorityQueue<Node>{ a, b ->
        when{
            a.cnt < b.cnt -> -1
            a.cnt == b.cnt -> 0
            else -> 1
        }
    }
    pq.add(Node(sr,sc,sd,0))

    while(pq.isNotEmpty()){
        val cur = pq.poll()
        for(i in 0 until 4){
            var nCnt = if(cur.d == i) cur.cnt else cur.cnt+1
            //두 번 돌려야 하는 경우
            if((cur.d+i)%4==1) nCnt++
            //end
            if(i==ed && cur.r == er && cur.c == ec) return nCnt
            if(visited[i][cur.r][cur.c]<nCnt) continue
            //go 1,2,3
            for(j in 1 .. 3){
                val nr = cur.r + dir[i][0]*j
                val nc = cur.c + dir[i][1]*j
                if(nr !in 0 until n || nc !in 0 until m) continue
                if(graph[nr][nc]=='1') break
                if(visited[i][nr][nc] <= nCnt+1) continue
                visited[i][nr][nc] = nCnt+1
                pq.add(Node(nr,nc,i,nCnt+1))
            }
        }
    }
    return -1
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m) = getIntList()
    graph = Array(n){br.readLine().split(' ').map{it[0]}.toCharArray()}
    visited = Array(4){Array(n){ IntArray(m){Int.MAX_VALUE} } }
    val (sr,sc,sd) = getIntList()
    val (er,ec,ed) = getIntList()
    //solve,output
    write("${bfs(sr-1,sc-1,sd-1,er-1,ec-1,ed-1,n,m)}")
    close()
}