[Joco][백준/BOJ] 1175 번: 배달

[문제]

1175번: 배달

[깃허브]

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

 

문제 요약

• 민식이가 목적지 두 곳에 모두 배달을 완료하기 위한 최단 거리 구하기
• 단, 이동할 때마다 방향을 계속 바꿔줘야 한다

제한 조건

• 시간 제한: 2
• 메모리 제한: 128MB
• 1 ≤ N, M ≤ 50 (N: 가로, M: 세로)

풀이

• BFS로 최단거리 구하는 문제
• 문제에 주어지는 목적지 두 곳(C)를 편의상 C와 D로 치환
• 이동 경로의 중복을 방지하기 위해 visited 활용
• (핵심1) 다음 칸으로 이동 할 때, 직전 방향은 제외하면서 진행
• (핵심2) 특정 위치에 대한 이동 경로 중복 조건에는 진입 방향(dir)과 목적지에 대한 상태(s) 정보를 추가로 확인
  • visited[s][r][c][d]: BooleanArray[3][N][M][4]
  • s=0: S -> C
  • s=1: C -> D
  • s=2: D -> C
  • 위 처럼 가고자 하는 목적지에 따라 세 가지 상태로 분류해야 함.
  • r: row, c: col, d: dirction

 

[Solution.kt]

import java.util.ArrayDeque

val MR = intArrayOf(0, -1, 0, 1) // move row
val MC = intArrayOf(-1, 0, 1, 0) // move col

fun main() {
    val input = readLine()!!.split(" ")
    val N = input[0].toInt() // 세로 크기
    val M = input[1].toInt() // 가로 크기

    val map = Array(N) { CharArray(M) }

    var cnt = 0
    for (r in 0 until N) {
        map[r] = readLine()!!.toCharArray()

        for (c in map[r].indices) {
            if (map[r][c] == 'C') {
                if (cnt == 0) cnt++
                else map[r][c] = 'D' // 두 번째 목적지를 'D'로 치환
            }
        }
    }

    solution(map, N, M).let { println(it) }
}

fun solution(map: Array<CharArray>, N: Int, M: Int): Int {
    val rangeR = 0 until N
    val rangeC = 0 until M

    val (sr, sc) = map.find { it == 'S' } // 민식이의 초기 위치(sr, sc)

    // visited[s][r][c][d]
    // s=0: S -> C 까지의 경로
    // s=1: C -> D
    // s=2: D -> C
    // r: row, c: col, d: direction
    val visited = Array(3) { Array(N) { Array(M) { BooleanArray(4) } } }
    for (d in 0 until 4) visited[0][sr][sc][d] = true

    val queue = ArrayDeque<IntArray>()
    queue.offer(intArrayOf(0, sr, sc, -1)) // 출발지

    var count = 0
    while (queue.isNotEmpty()) { // BFS
        count++

        for (i in queue.indices) { // 큐 한 사이클 돌기
            val (s, r, c, d) = queue.poll()

            for (dn in 0 until 4) { // 상, 하, 좌, 우 이동
                if (d == dn) // 기존 방향 제외
                    continue

                val rn = r + MR[dn]
                val cn = c + MC[dn]

                if (rn !in rangeR || cn !in rangeC || map[rn][cn] == '#' || visited[s][rn][cn][dn])
                    continue

                val block = map[rn][cn]

                if (block == 'C' || block == 'D') {
                    if (s == 0) { // 목적지 첫 번째 도착
                        val next = if (block == 'C') 1 else 2

                        // 방금 거쳐간 목적지에 다시 들어오지 않게 하기
                        for (j in 0 until 4)
                            visited[next][rn][cn][j] = true

                        queue.offer(intArrayOf(next, rn, cn, dn))
                    } else { // 두 번째 목적지 도착
                        return count
                    }
                } else {
                    visited[s][rn][cn][dn] = true
                    queue.offer(intArrayOf(s, rn, cn, dn))
                }
            }
        }
    }

    return -1
}

private fun Array<CharArray>.find(predicate: (Char) -> Boolean): Pair<Int, Int> {
    for (r in indices) for (c in this[r].indices)
        if (predicate(this[r][c])) return r to c
    return -1 to -1
}