백준 4991 로봇 청소기 Kotlin (완탐, 비트마스킹)

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

4991번: 로봇 청소기

문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 비트마스킹

풀이

크게 3가지 풀이가 가능하다고 한다.

1. 완탐 + bfs/dfs

2. 비트마스킹 + dp

3. 외판원 순회 알고리즘

 

본인은 완탐으로 풀었다.

이 문제에서 완탐의 의미는 더러운 칸을 가능한 모든 순서로 탐색함을 의미한다.

더러운 칸의 최대 개수는 10

10개로 가능한 경우의 수는 10!이고 거리를 구하는 것도 그래프가 최대 20*20의 크기이기 때문에 통과 가능하다.

풀이 순서는 다음과 같다.

1. 더러운 칸을 모두 저장한다.

2. 더러운 칸에서 다른 더러운 칸으로 가는 Edge를 만든다.

3. Edge를 만들 때 더러운 칸과 더러운 칸 사이의 최소 거리를 구하기 위해 Bfs를 이용한다.

4. 이때 더러운 칸에서 더러운 칸으로 이동할 수 없는 경우 모든 더러운 칸을 청소할 수 없음을 의미하기 때문에 -1을 출력하고 끝낸다.

5. edge를 구해놨으니 이제 로봇의 시작 칸 부터 가능한 모든 더러운 칸 방문 순서로 더러운 칸을 방문하며 이동 거리를 누적한다.(완탐)

6. 모든 더러운 칸을 방문했으면 거리의 최솟값을 갱신한다.

 

내일은 비트마스킹으로 풀어봐야지

 

오늘은 비트마스킹으로 풀어봤다.

코드도 훨씬 짧고 효율적이다.

요즘 문제를 많이 안 풀어서 비트마스킹이 떠오르지 않았었는데 코테에 이런 문제가 나온다면 비트마스킹으로 빠르게 풀고 넘어가자.

 

우선 첫 번째 입력 7 5를 예로 들면,

더러운 칸이 총 3개이다.

그럼 우리는 3개의 칸이 이 3개의 dirty를 청소했는지 안 했는지 판별할 수 있지 않을까?

dirty a,b,c가 있다고 하고 a부터 왼쪽이라고 하자.

1은 청소한 상태, 0은 청소하지 않은 상태라고 하면

0,0,0

0,0,1

0,1,0

0,1,1

1,0,0

1,0,1

1,1,0

1,1,1

이런 식으로 더러운 칸들의 방문(청소) 여부를 체크할 수 있다.

1,1,1 상태는 곧 모든 더러운 칸을 청소했음을 의미하고 우리가 원하는 건 이 상태로 만드는 데에 걸리는 최단 거리이다.

그렇다. 최단 거리엔 bfs를 이용하면 되고, bfs에서 중복 탐색을 막는 visited에 이 개념을 도입하면 된다.

우리는 위의 0과 1의 상태들에 비트마스킹을 사용한다.

위 상태들을 2진법이라고 생각해 보자.

0,0,1은 1

1,0,1은 5

1,1,1은 7

 

3개의 dirty가 있을 때 8(2^3)개의 상태가 존재하고, 이를 2진법으로 생각하여 10진법으로 계산하면 1부터 7까지이다.

즉, 크기가 8인 배열로 8개의 상태일 때의 그래프 visited 상태를 알 수 있는 것이다.

visited = Array(1 shl dirty개수){Array(n){BooleanArray(m)}}

위처럼 방문 체크 배열 visited를 2차원이 아닌 8개의 상태에 대해 각각 방문 체크 배열을 만들어 중복 탐색을 막는다.

예를 들어 b,c를 청소한 상태(0,1,1(3))에서 (0,5)칸을 방문했다고 치자.

럼 c를 청소한 상태(0,0,1(1))에서 (0,5)칸을 재방문했을 때는 정상적으로 탐색하고,

b,c를 청소한 상태(0,1,1(3))에서 (0,5)칸을 재방문했을 때는 스킵하는 것이다.

 

핵심은 더러운 칸을 방문한 상태별로 2차원 visited를 두어

2차원이 아닌 3차원 체크로 한 번의 Bfs로 모든 더러운 칸을 청소 + 마지막 남은 더러운 칸을 방문하는 최단 거리를 구해내는 것이다.

이 부분은 주관적인 주관적인 해석이므로 이 말이 이해되지 않아도 괜찮다. 본인의 입맛대로 해석하면 된다.

 

무튼 이제 쉽다 bfs에서  더러운 칸을 만나면 아래와 같은 테크닉만 사용해 주면 된다.

b를 청소한 상태 (0,1,0(2)) 에서 c를 청소하게 된다면 (0,1,1(3))이 되는 것을 생각하면 된다.

실제 dirty를 나타내는 abc는 본인 입맛대로 구현하면 된다. 본인은 인덱스를 사용했다.

            if (graph[nr][nc] == '*') {
                ns = cs or (1 shl dirty[nr][nc])
            }

 

 

코드1 (완탐)

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

data class Node(
    val r: Int,
    val c: Int,
)

lateinit var graph: Array<String>
lateinit var dests: MutableList<Node>
lateinit var edge: Array<IntArray>
var answer = 0
val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0),
)

fun main() = with(System.out.bufferedWriter()) {
    while (true) {
        //input
        answer = Int.MAX_VALUE
        val (m, n) = getIntList()
        var start = 0
        if (n == 0 && m == 0) break
        dests = mutableListOf()
        graph = Array(n) { r ->
            val line = br.readLine()
            for (c in line.indices) {
                if (line[c] == 'o') {
                    dests.add(Node(r, c))
                    start = dests.size - 1
                } else if (line[c] == '*') {
                    dests.add(Node(r, c))
                }
            }
            line
        }
        //solve
        if(!makeEdge(n, m)){
            write("-1\n")
        }else {
            val visited = BooleanArray(dests.size)
            visited[start] = true
            permutation(1, start, 0, visited)
            //output
            write("$answer\n")
        }
    }
    close()
}

fun permutation(cnt: Int, cur: Int, dis: Int, visited: BooleanArray) {
    if (cnt == dests.size) {
        answer = answer.coerceAtMost(dis)
        return
    }

    for (next in dests.indices) {
        if (visited[next]) continue
        visited[next] = true
        permutation(cnt + 1, next, dis + edge[cur][next], visited)
        visited[next] = false
    }
}

fun makeEdge(n: Int, m: Int): Boolean {
    edge = Array(dests.size) { IntArray(dests.size) }
    for (from in dests.indices) {
        for (to in dests.indices) {
            if (from == to) continue
            edge[from][to] = bfs(from, to, n, m)
            if(edge[from][to] == 0) return false
        }
    }
    return true
}

fun bfs(from: Int, to: Int, n: Int, m: Int): Int {
    val q: Queue<Triple<Int, Int, Int>> = LinkedList()
    val visited = Array(n) { BooleanArray(m) }
    val (r, c) = dests[from]
    q.add(Triple(r, c, 0))
    visited[r][c] = true
    val (er, ec) = dests[to]
    while (q.isNotEmpty()) {
        val (cr, cc, dis) = q.poll()
        for (i in 0 until 4) {
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]
            if (nr !in 0 until n || nc !in 0 until m) continue
            if (visited[nr][nc]) continue
            if(graph[nr][nc] == 'x') continue
            if (nr == er && nc == ec) return dis + 1
            q.add(Triple(nr, nc, dis + 1))
            visited[nr][nc] = true
        }
    }
    return 0
}

코드2 (비트 마스킹)

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

lateinit var graph: Array<String>
lateinit var dirty: Array<IntArray>
lateinit var visited: Array<Array<IntArray>>

val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0),
)

data class Node(
    val r: Int,
    val c: Int,
    val state: Int,
)

fun main() = with(System.out.bufferedWriter()) {
    //input
    while (true) {
        val (m, n) = getIntList()
        if (n == 0 && m == 0) break
        var cnt = 0
        var sr = 0
        var sc = 0
        dirty = Array(n){ IntArray(m) }
        graph = Array(n) { r ->
            val line = br.readLine()
            for (c in line.indices) {
                if (line[c] == '*') {
                    dirty[r][c] = cnt++
                } else if (line[c] == 'o') {
                    sr = r
                    sc = c
                }
            }
            line
        }
        visited = Array(1 shl cnt) { Array(n) { IntArray(m) } }
        write("${bfs(sr, sc, n, m)}\n")
    }

    close()
}

fun bfs(sr: Int, sc: Int, n: Int, m: Int): Int {
    val q: Queue<Node> = LinkedList()
    q.add(Node(sr, sc, 0))
    while (q.isNotEmpty()) {
        val (cr, cc, cs) = q.poll()
        for (i in 0 until 4) {
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]
            var ns = cs
            if (nr !in 0 until n || nc !in 0 until m) continue
            if (graph[nr][nc] == 'x') continue
            if (graph[nr][nc] == '*') {
                ns = cs or (1 shl dirty[nr][nc])
            }
            if (visited[ns][nr][nc] > 0) continue
            if (ns == visited.size-1){
                return visited[cs][cr][cc] + 1
            }
            visited[ns][nr][nc] = visited[cs][cr][cc] + 1
            q.add(Node(nr, nc,ns))
        }
    }
    return -1
}