[백준 1385번] [Kotlin] 벌집

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

1385번: 벌집

 

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

 

 

1. 설명

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

 

 

 

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

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

 

 

 

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

 

 

그래프는 위와 같이 벌집을 약간 회전시켜 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.2. 근데 어떻게 그래프 형태로 나타내지?

 

 

 

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

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

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

 

 

      

      

      

    
    

      <kotlin />
    
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쯤에서 표현이 가능하더군요.

 

 

 

1.3. BFS로 최단거리 탐색 시작

      

      

      

    
    

      <kotlin />
    
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에 직전 좌표를 저장합니다.

 

 

 

1.4. 경로 역추적

      

      

      

    
    

      <kotlin />
    
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일 때 까지 반복합니다.

 

 

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
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
}

 

 

 

3. 후기

벌집 BFS는 또 첨이네요.

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

풀고 나니 상쾌합니다.