[Joco][백준/BOJ] 1385 번: 벌집 - Kotlin

[문제]

1385번: 벌집

[깃허브]

GitHub - Dev-Joco/algorithm-kotlin: Algorithm(Kotlin)

 

 

문제 요약

• 정육각형으로 빈틈없이 채워진 벌집 모양의 그리드에서 방과 방 사이의 최단경로를 구하는 문제

 

제한 조건

• 시간 제한: 2초
• 메모리 제한: 128MB
• 시작 지점: a, 도착 지점: b (1 ≤ a, b ≤ 1,000,000)

 

 

삼성 노트로 그린 벌집 노드간의 간선

풀이

• 각각의 방에서 인접한 6개의 방 번호를 그래프로 표현한 뒤 BFS와 Back Tracking으로 최단경로 구하기
• 매우 규칙적인 것 같으면서도 막상 그래프로 표현하기가 쉽지 않기 때문에 벌집의 몇가지 특징을 잡기 위해 직접 그림을 그려보았다
  1. 안쪽부터 차례로 각각의 노란색 선에 분포된 방의 갯수:  An = 6n (n = 1, 2, 3...)
  2. n번째 노란 육각줄의 마지막 번호, 즉 An의 누적 합: Sn = 1 + ∑An = 1 + 6*n(n+1)/2
  3. 파란색 점으로 표시된 방들은 각 노란 육각줄의 꼭짓점을 나타내며, 이를 토대로 모든 방은 두 가지로 분류된다.
     • 꼭짓점의 방은 인접한 6개의 방이 (부모, 형제, 자식) = (1, 2, 3) 개 이다.
     • 꼭짓점이 아닌 방은 인접한 6개의 방이 (부모, 형제, 자식) = (2, 2, 2) 개 이다.
• 위 3가지 특징을 잘 이용하여 1번 방부터 순차적으로 인접해 있는 방들의 번호를 기록해가며 그래프 정보를 저장한 후 주어진 두 개의 방 번호로 BFS 탐색을 한다
• (주의) 메모리 제한이 128MB 인데, graph[N][6] 정수 배열만 해도 자바에서는 최대 72MB 나오므로 주의해야 한다.

 

 

* 저는 이 문제의 벌집 그래프에 대한 정보가 항상 동일하기 때문에 전역 필드에서 상한값 100만개(벌집을 모두 다 채우면 557개의 노란 육각형 라인과 1,000,519개)의 2차원 그래프 정수 배열을 초기화하였습니다.

 

 

[Solution.kt]

import java.util.ArrayDeque

private const val MAX = 1_000_519
private const val MAX_LEN = 577

private val graph: Array<IntArray> = makeGraph()

fun main() {
    // (1 ≤ from, to ≤ 1,000,000)
    val (from, to) = readln().split(" ").map { it.toInt() }.toIntArray()

    solution(from, to).let { println(it) }
}

private fun solution(from: Int, to: Int): String {
    if (from == to)
        return from.toString()

    val queue = ArrayDeque<Int>()
    val back = IntArray(graph.size)

    queue.offer(from)
    back[from] = -1

    while (queue.isNotEmpty()) {
        val curr = queue.poll()

        for (next in graph[curr]) {
            if (back[next] != 0)
                continue

            back[next] = curr

            if (next == to) {
                queue.clear()
                break
            }

            queue.offer(next)
        }
    }

    return back.tracking(to)
}

private fun IntArray.tracking(last: Int): String {
    val sb = StringBuilder()
    var n = last
    while (n != -1) {
        sb.insert(0, "$n ")
        n = this[n]
    }
    return sb.deleteCharAt(sb.lastIndex).toString()
}

private fun makeGraph(): Array<IntArray> {
    val isVertex = BooleanArray(MAX + 1)

    // 꼭지점인 지역 체크
    for (start in 2..7) {
        var n = start // 시작점(2 ~ 7)
        var d = start + 5 // 공차

        while (n <= MAX) {
            isVertex[n] = true
            n += d
            d += 6
        }
    }

    val graph = Array(MAX + 1) { IntArray(6) }
    val idx = IntArray(MAX + 1)

    // 1번 노드와 1번째 형제 노드들과 연결
    for (n in 2..7) {
        graph[1][n - 2] = n
    }

    var preRange = 1..1
    var curRange = 2..7
    for (len in 1..MAX_LEN) {

        var pn1 = preRange.last
        var pn2 = preRange.first
        var n = curRange.first

        for (i in curRange) {

            // 부모(이전육각형) 노드와 그래프 연결
            if (isVertex[n]) { // 육각형의 꼭지점 노드
                graph[n][idx[n]++] = pn1
                graph[pn1][idx[pn1]++] = n
            } else { // 꼭지점 사이의 노드
                graph[n][idx[n]++] = pn1
                graph[n][idx[n]++] = pn2

                graph[pn1][idx[pn1]++] = n
                graph[pn2][idx[pn2]++] = n

                pn1 = if (pn1 == preRange.last) preRange.first else pn1 + 1
                pn2 += 1
            }

            // 형제(현재육각형) 노드와 그래프 연결
            graph[n][idx[n]++] = if (n - 1 !in curRange) curRange.last else n - 1
            graph[n][idx[n]++] = if (n + 1 !in curRange) curRange.first else n + 1

            n += 1
        }

        preRange = curRange
        curRange = (curRange.last + 1)..(sum(len + 1))
    }

    return graph
}

/** n번째 육각형 그룹의 마지막 노드 번호(누적 합) */
private fun sum(n: Int): Int {
    return 3 * n * (n + 1) + 1
}