[백준 16985번] [Kotlin] Maaaaaaaaaze

https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

 

난이도 : 골드 2
태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색

 

 

설명

3차원 큐브를 탈출하는 문제입니다.

 

한 층씩 좌우로 층을 회전할 수 있고,

한 층씩 마음대로 쌓을 수 있기 때문에,

 

각 층을 회전하여 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS) 1번,

각 층을 쌓아 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS) 1번,

큐브의 층을 회전하고, 쌓아 많든 큐브에서 탈출하기 위한 BFS 1번.

총 3번의 탐색을 사용하였습니다.

 

 

 

소스코드

각각의 층 회전하는 경우의 수

fun floorRotateSearch(depth: Int, map: Array<Array<IntArray>>) {
    if (depth == 5) {
        val copiedMap = Array(n) { x -> Array(n) { y -> IntArray(n) { z -> map[x][y][z] } } }
        floorStackSearch(0, BooleanArray(5), map, copiedMap)
        return
    }

    for (i in 0..4) {
        floorRotate(map, depth)
        floorRotateSearch(depth + 1, map)
    }
}

fun floorRotate(map: Array<Array<IntArray>>, floor: Int) {
    val temp = Array(n) { x -> IntArray(n) { y -> map[floor][x][y] } }

    for (i in 0 until n) {
        for (j in 0 until n) {
            map[floor][i][j] = temp[n - 1 - j][i]
        }
    }
}

 

DFS를 사용하여 1~5층을 회전하여 만들 수 있는 모든 경우의 수를 찾습니다.

층을 회전하는 함수는 floorRotate로, 시계 방향으로 90도 회전합니다.

 

 

 

각각의 층을 쌓는 경우의 수

fun floorStackSearch(depth:Int, visited:BooleanArray, originMap: Array<Array<IntArray>>, copiedMap: Array<Array<IntArray>>) {
    if(depth == 5) {
        if(copiedMap[0][0][0] == 0 || copiedMap[4][4][4] == 0) return
        min = minOf(min, bfs(copiedMap))
        return
    }

    for(i in 0 until 5) {
        if(visited[i]) continue

        visited[i] = true
        copiedMap[depth] = originMap[i].copyOf()
        floorStackSearch(depth+1, visited, originMap, copiedMap)
        visited[i] = false
    }
}

 

floorRotateSearch에서 한 경우의 수를 찾았다면 맵을 복사하여 원본맵과 함께 floorStackSearch에 넘겨줍니다.

floorStackSearch 메소드는 dfs로 층을 쌓는 경우의 수를 찾는 메소드로써,

입구와 출구가 갈 수 있는 곳이라면(==0) bfs로 미로를 탈출할 수 있는지 확인합니다.

 

 

 BFS로 미로 탈출 경로 찾기

val dx = intArrayOf(0, 0, 0, 0, 1, -1)
val dy = intArrayOf(0, 0, 1, -1, 0, 0)
val dz = intArrayOf(1, -1, 0, 0, 0, 0)

-- 중략 --

fun bfs(map: Array<Array<IntArray>>): Int {
    val visited = Array(n) { Array(n) { IntArray(n) } }
    val queue = ArrayDeque<Triple<Int, Int, Int>>()

    queue.addFirst(Triple(0, 0, 0))
    visited[0][0][0] = 1

    while (queue.isNotEmpty()) {
        val target = queue.removeLast()

        for (i in 0 until 6) {
            val nx = target.first + dx[i]
            val ny = target.second + dy[i]
            val nz = target.third + dz[i]

            if (nx !in 0 until n || ny !in 0 until n || nz !in 0 until n ||
                map[nx][ny][nz] == 0 || visited[nx][ny][nz] != 0
            ) continue

            if (nx == 4 && ny == 4 && nz == 4) return visited[target.first][target.second][target.third]

            visited[nx][ny][nz] = visited[target.first][target.second][target.third] + 1
            queue.addFirst(Triple(nx, ny, nz))
        }
    }

    return Int.MAX_VALUE
}

 

해당 부분은 3차원 상에서 진행되는 것 말고는

2차원 미로찾기 BFS와 동일한 로직을 갖고 있습니다.

 

Triple은 Pair와 같이 3개의 원소를 담는 자료구조로,

x, y, z를 멤버변수로 갖고 있는 데이터용 클래스를 사용하여도 무방합니다.

 

 

전체 소스코드

val dx = intArrayOf(0, 0, 0, 0, 1, -1)
val dy = intArrayOf(0, 0, 1, -1, 0, 0)
val dz = intArrayOf(1, -1, 0, 0, 0, 0)
var min = Int.MAX_VALUE
const val n = 5

fun main() = with(System.`in`.bufferedReader()) {
    val map = Array(n) { Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() } }
    floorRotateSearch(0, map)
    println(if (min == Int.MAX_VALUE) -1 else min)
}

fun floorRotateSearch(depth: Int, map: Array<Array<IntArray>>) {
    if (depth == 5) {
        val copiedMap = Array(n) { x -> Array(n) { y -> IntArray(n) { z -> map[x][y][z] } } }
        floorStackSearch(0, BooleanArray(5), map, copiedMap)
        return
    }

    for (i in 0..4) {
        floorRotate(map, depth)
        floorRotateSearch(depth + 1, map)
    }
}

fun floorStackSearch(depth:Int, visited:BooleanArray, originMap: Array<Array<IntArray>>, copiedMap: Array<Array<IntArray>>) {
    if(depth == 5) {
        if(copiedMap[0][0][0] == 0 || copiedMap[4][4][4] == 0) return
        min = minOf(min, bfs(copiedMap))
        return
    }

    for(i in 0 until 5) {
        if(visited[i]) continue

        visited[i] = true
        copiedMap[depth] = originMap[i].copyOf()
        floorStackSearch(depth+1, visited, originMap, copiedMap)
        visited[i] = false
    }
}

fun bfs(map: Array<Array<IntArray>>): Int {
    val visited = Array(n) { Array(n) { IntArray(n) } }
    val queue = ArrayDeque<Triple<Int, Int, Int>>()

    queue.addFirst(Triple(0, 0, 0))
    visited[0][0][0] = 1

    while (queue.isNotEmpty()) {
        val target = queue.removeLast()

        for (i in 0 until 6) {
            val nx = target.first + dx[i]
            val ny = target.second + dy[i]
            val nz = target.third + dz[i]

            if (nx !in 0 until n || ny !in 0 until n || nz !in 0 until n ||
                map[nx][ny][nz] == 0 || visited[nx][ny][nz] != 0
            ) continue

            if (nx == 4 && ny == 4 && nz == 4) return visited[target.first][target.second][target.third]

            visited[nx][ny][nz] = visited[target.first][target.second][target.third] + 1
            queue.addFirst(Triple(nx, ny, nz))
        }
    }

    return Int.MAX_VALUE
}

fun floorRotate(map: Array<Array<IntArray>>, floor: Int) {
    val temp = Array(n) { x -> IntArray(n) { y -> map[floor][x][y] } }

    for (i in 0 until n) {
        for (j in 0 until n) {
            map[floor][i][j] = temp[n - 1 - j][i]
        }
    }
}

 

 

 

후기

풀이 아이디어 자체는 완전탐색  + 완전탐색 + BFS로 금방 떠올리긴 했지만,

구현이 생각보다 쉽지 않았던 문제였습니다.

3차원 탐색은 종종 해봤지만,

이런 문제는 또 처음이네요.