[백준 1385번] [Kotlin] 벌집

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

1385번: 벌집

 

난이도 : 플래티넘 5
태그 : 구현, 그래프이론, 그래프탐색, 너비우선탐색

 

 

설명

벌집(2292)에 비해 꽤나 매운맛인 벌집 문제 입니다.

 

 

 

위와 같이 생긴 벌집을 대상으로 최단거리를 찾는 BFS을 돌려 풀 수 있겠다는 생각은 빨리 들었으나,

벌집의 모양을 그래프로 나타내는 것에 상당히 어려움을 느꼈습니다. 

 

 

 

벌집을 그래프로 나타내라!

 

 

그래프는 위와 같이 벌집을 약간 회전시켜 2차원 배열 형태로 나타낼 수 있습니다.

예를 들어 500 * 500 사이즈 배열의 경우,

(250, 250)을 1로 잡아놓고,

(상, 우측상단, 우, 하, 좌측하단, 좌)  순서대로 2~7을 채워넣고,

그 다음 층에 8~19를 채워놓고,

그 다음 20 ~ 37을 채워놓는 방식입니다.

 

이렇게 그래프(좌표)화를 시켜놓는다면

한 점을 콕 집었을 때 6방향에 대해 인접한 벌집의 칸을 확인할 수 있습니다.

 

 

17을 콕 찝었을 때, 좌측 벌집은 6, 16, 33, 34, 35, 18가 인접합니다.

좌표화를 진행한 오른쪽 그림 역시 17번을 콕 찝었을 때,

역시 상-우측상단-우-하-좌측하단-좌 방향에 18-6-16-33-34-35로

동일한 숫자들이 인접한 것을 볼 수 있습니다.

 

 

 

근데 어떻게 그래프 형태로 나타내지?

 

 

 

좌표화한 벌집을 보면 ↗→↓↙←↑ 으로 이동하며 숫자가 커지는 것을 볼 수 있습니다.

1을 1층, 2~7을 2층이라 했을 때,

각 방향의 이동횟수는 (층 - 1)번 만큼 이동하며 숫자를 찍습니다.

 

 

const val MAP_SIZE = 1200  
  
val map = Array(MAP_SIZE) { IntArray(MAP_SIZE) { 0 } }

map[MAP_SIZE / 2][MAP_SIZE / 2] = 1

var num = 2
var x = MAP_SIZE / 2
var y = MAP_SIZE / 2 - 1

var dir = 0
var layer = 1

val mapGeneratorDx = intArrayOf(-1, 0, 1, 1, 0, -1)
val mapGeneratorDy = intArrayOf(1, 1, 0, -1, -1, 0)

while (num <= 1000000) {
    for (i in 0..<layer) {
        x += mapGeneratorDx[dir]
        y += mapGeneratorDy[dir]
        map[x][y] = num++
    }
    dir = (dir + 1) % 6
    if (dir == 0) {
        layer++
        y--
    }
}

 

 

↗→↓↙←↑ 를 표현하기 위해 아래와 같이 dx와 dy를 잡아줬습니다.

val mapGeneratorDx = intArrayOf(-1, 0, 1, 1, 0, -1)
val mapGeneratorDy = intArrayOf(1, 1, 0, -1, -1, 0)

 

이후 각 방향에 층(layer) - 1번 만큼 이동하고,

여섯 방향에 대해 모두 숫자 생성을 마쳤다면

층을 하나 증가시킵니다.

 

또, 위 코드에서 첫 방향을 ↗로 잡았기에

y를 1만큼 감소시켜 왼쪽으로 한 칸 이동하여 바로 ↗방향으로 숫자를 생성할 수 있도록 합니다.

 

 

배열 사이즈의 경우에는,

숫자의 범위가 1 ~ 1,000,000이길래 배열 크기를 어떻게 잡을지 고민해봤는데,

그냥 조금씩 늘리면서 indexOutRange가 나지 않을 때 까지 배열 사이즈를 조금씩 늘려보니,

1200 * 1200쯤에서 표현이 가능하더군요.

 

 

 

BFS로 최단거리 탐색 시작

fun bfsAndGeneratePrePath(map: Array<IntArray>, startNode: Node, endNode: Node): Array<Array<Node?>> {
    val bfsDx = intArrayOf(-1, -1, 0, 1, 1, 0)
    val bfsDy = intArrayOf(0, 1, 1, 0, -1, -1)

    val queue = ArrayDeque<Node>()
    val visited = Array(MAP_SIZE) { BooleanArray(MAP_SIZE) { false } }
    val prePath = Array(MAP_SIZE) { Array<Node?>(MAP_SIZE) { null } }

    queue.add(Node(startNode.x, startNode.y))
    visited[startNode.x][startNode.y] = true

    bfs@ while (queue.isNotEmpty()) {
        val (curX, curY) = queue.removeFirst()

        for (i in 0 until 6) {
            val nx = curX + bfsDx[i]
            val ny = curY + bfsDy[i]

            if (visited[nx][ny] || map[nx][ny] == 0) continue
            visited[nx][ny] = true
            queue.add(Node(nx, ny))
            prePath[nx][ny] = Node(curX, curY)

            if (nx == endNode.x && ny == endNode.y) {
                break@bfs
            }
        }
    }

    return prePath
}

 

어려운 부분은 다 끝냈으니 bfs를 돌려 최단 경로를 탐색합시다.

단, 최단거리의 값를 출력하는 것이 아닌, 지나쳐온 경로를 출력하는 것이기에

이전 좌표를 저장할 prePath도 추가해줬습니다.

bfs를 수행하며 prePath에 직전 좌표를 저장합니다.

 

 

 

경로 역추적

fun findPath(map: Array<IntArray>, endNode: Node, prePath: Array<Array<Node?>>): ArrayDeque<Int> {
    val path = ArrayDeque<Int>()
    var preNode = endNode

    path.addFirst(map[preNode.x][preNode.y])

    while (true) {
        val nowNode = prePath[preNode.x][preNode.y] ?: break
        path.addFirst(map[nowNode.x][nowNode.y])
        preNode = nowNode
    }

    return path
}

 

도착 노드에서 시작해 이전 좌표를 담고 있는 prePath의 값을 추적해나갑니다.

저는 ArrayDeque를 사용해 새롭게 탐색하는 방의 숫자를 Deque의 맨 앞에 넣어줬습니다.

시작점의 이전 좌표는 null일 것이기에, 위 과정을 prePath의 값이 null일 때 까지 반복합니다.

 

 

 

 

소스코드

data class Node(var x: Int, var y: Int)

const val MAP_SIZE = 1200

fun main() {
    val (startPoint, endPoint) = readln().split(" ").map { it.toInt() }
    if (startPoint == endPoint) {
        println(startPoint)
        return
    }

    val map = generateHoneycombMap()

    var startNode = Node(-1, -1)
    var endNode = Node(-1, -1)

    for (i in 0 until MAP_SIZE) {
        for (j in 0 until MAP_SIZE) {
            if (map[i][j] == startPoint) {
                startNode = Node(i, j)
            }
            if (map[i][j] == endPoint) {
                endNode = Node(i, j)
            }
        }
    }

    val prePath = bfsAndGeneratePrePath(map, startNode, endNode)
    val path = findPath(map, endNode, prePath)

    println(path.joinToString(" "))
}

fun findPath(map: Array<IntArray>, endNode: Node, prePath: Array<Array<Node?>>): ArrayDeque<Int> {
    val path = ArrayDeque<Int>()
    var preNode = endNode

    path.addFirst(map[preNode.x][preNode.y])

    while (true) {
        val nowNode = prePath[preNode.x][preNode.y] ?: break
        path.addFirst(map[nowNode.x][nowNode.y])
        preNode = nowNode
    }

    return path
}

fun bfsAndGeneratePrePath(map: Array<IntArray>, startNode: Node, endNode: Node): Array<Array<Node?>> {
    val bfsDx = intArrayOf(-1, -1, 0, 1, 1, 0)
    val bfsDy = intArrayOf(0, 1, 1, 0, -1, -1)

    val queue = ArrayDeque<Node>()
    val visited = Array(MAP_SIZE) { BooleanArray(MAP_SIZE) { false } }
    val prePath = Array(MAP_SIZE) { Array<Node?>(MAP_SIZE) { null } }

    queue.add(Node(startNode.x, startNode.y))
    visited[startNode.x][startNode.y] = true

    bfs@ while (queue.isNotEmpty()) {
        val (curX, curY) = queue.removeFirst()

        for (i in 0 until 6) {
            val nx = curX + bfsDx[i]
            val ny = curY + bfsDy[i]

            if (visited[nx][ny] || map[nx][ny] == 0) continue
            visited[nx][ny] = true
            queue.add(Node(nx, ny))
            prePath[nx][ny] = Node(curX, curY)

            if (nx == endNode.x && ny == endNode.y) {
                break@bfs
            }
        }
    }

    return prePath
}


fun generateHoneycombMap(): Array<IntArray> {
    val map = Array(MAP_SIZE) { IntArray(MAP_SIZE) { 0 } }

    map[MAP_SIZE / 2][MAP_SIZE / 2] = 1

    var num = 2
    var x = MAP_SIZE / 2
    var y = MAP_SIZE / 2 - 1

    var dir = 0
    var layer = 1

    val mapGeneratorDx = intArrayOf(-1, 0, 1, 1, 0, -1)
    val mapGeneratorDy = intArrayOf(1, 1, 0, -1, -1, 0)

    while (num <= 1000000) {
        for (i in 0..<layer) {
            x += mapGeneratorDx[dir]
            y += mapGeneratorDy[dir]
            map[x][y] = num++
        }
        dir++
        if (dir == 6) {
            dir = 0
            layer++
            y--
        }
    }

    return map
}

 

 

 

후기

벌집 BFS는 또 첨이네요.

꽤나 많은 시간을 들이긴 했지만

풀고 나니 상쾌합니다.