[백준] 14940 (쉬운 최단거리)

#1 알고리즘

#1-1 '최단 거리'의 의미

이 문제에서 '최단 거리'란, '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다.
 

1차원에서는 간단하다. 검은색 선의 길이와 '최단 거리'가 비례하기 때문이다 (이미 방문한 지역은 다시 방문하지 않는다).
 

2차원이라면 문제가 복잡해진다. 선의 길이와 '최단 거리'가 비례하지 않는다. 2에서 1로 가는 빨간색 선은 '최단 거리'면서 동시에 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 초록색 선은 '최단 거리'는 아니지만, 빨간색 선과 마찬가지로 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 정리하면, 2차원에서 '최단 거리'는 반드시 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이지만, 역으로 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이 '최단 거리'는 아니게 된다.
 

#1-2 순서

#1-1에서 초록색 순회보다 빨간색 순회를 먼저 수행한 뒤, 1에 '이미 방문함' 표시를 해놓는다면 초록색 선의 길이가 정답으로서 입력되는 일을 방지할 수 있을 것이다. 키워드는 먼저다. 2에 제일 가까운 지역을 먼저 방문하고, 이후 나머지 지역 또한 먼저 방문했던 지역으로부터 제일 가까운 지역을 방문하는 식으로 재귀적인 탐색을 수행한다. 이러면 모든 지역에 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'을 '최단 거리'로서 마킹할 수 있다.
 

#1-3 Queue

(먼저 들어온 순서대로 나오는) Queue를 선언하고 목표 지점(2)에서 가까운 지역부터 Queue에 넣고 방문한다. 이러면 #1-2에서 말한 '순서'를 지키며 순회할 수 있다.
 

#2 여담

그래프 - 너비 우선 탐색 (BFS, Breadth-First Search)

어떤 백준 문제든 정답을 맞히기 전까지는, '알고리즘 분류'를 보지 않으려고 노력한다. 문제 풀이에 강력한 스포일러가 되기 때문이다. 이 문제도 그렇다. 풀고 나서 '알고리즘 분류'를 봤는데, 그래프 이론이었다. 나는 그저 Queue를 활용했을 뿐, 그래프 문제를 푼다는 자각을 전혀 가지지 않고 문제를 풀었는데 말이다. 이 문제가 그래프 문제라는 걸 알았다면 Queue를 도입할 생각을 어렵지 않게 떠올렸을 것이다 (그러지 못해서 Queue를 활용하기까지 시간이 꽤 소모됐다).
 
꼭 트리 구조에서만 그래프 이론이 적용되는 게 아니라는 교훈을 얻었다. 어떤 자료 구조에서든 너비 우선 탐색은 그저 Queue를 활용한 순회일 뿐이고, 깊이 우선 탐색은 그저 Stack을 활용한 순회일 뿐인 것이다.
 

#3 코드 - 코틀린

import java.util.*

var n = -1 // 세로 (y축)
var m = -1 // 가로 (x축)
lateinit var map: Array<Array<Int>>
val remainingDestinations: Queue<Array<Int>> = LinkedList()
var target = Pair(-1, -1)

/*
map의 원소
-3: 이동 불가능
-2: 이동 가능
-1: target
0 이상: target으로부터의 거리
*/
fun main() {
    // 초기화
    val nAndM = readln().split(" ")
    n = nAndM[0].toInt()
    m = nAndM[1].toInt()
    map = Array(n) { Array(m) { -1 } }

    for (i: Int in 0..<n) {
        val row = readln().split(" ")

        for (j: Int in 0..<m) {
            val element = row[j].toInt() - 3
            map[i][j] = element
            if (element == -1) {
                target = Pair(i, j)
            }
        }
    }

    // 맵 순회
    remainingDestinations.add(arrayOf(target.first, target.second, -1))
    while (!remainingDestinations.isEmpty()) {
        val location = remainingDestinations.poll()
        visit(location)
    }

    // 출력
    for (i: Int in 0..<n) {
        for (j: Int in 0..<m) {
            when (map[i][j]) {
                -3 -> print("0 ")
                -2 -> print("-1 ")
                else -> print("${map[i][j]} ")
            }
        }
        println()
    }
}

fun visit(location: Array<Int>) {
    val y = location[0]
    val x = location[1]
    val distanceFromTargetOfPreviousLocation = location[2]

    if (0 <= map[y][x]) { // (Queue에 add된 후 ~ poll되기 전)에 이미 다른 순회에서 방문한 경우라면 생략
        return
    }

    map[y][x] = distanceFromTargetOfPreviousLocation + 1

    // 동 (x + 1)
    if (isMovable(y, x + 1)) {
        remainingDestinations.add(arrayOf(y, x + 1, map[y][x]))
    }

    // 서 (x - 1)
    if (isMovable(y, x - 1)) {
        remainingDestinations.add(arrayOf(y, x - 1, map[y][x]))
    }

    // 남 (y + 1) y축은 x축과 달리 내림차순으로 입력되었으므로 남쪽은 (y - 1)이 아니라 (y + 1)다.
    if (isMovable(y + 1, x)) {
        remainingDestinations.add(arrayOf(y + 1, x, map[y][x]))
    }

    // 북 (y - 1)
    if (isMovable(y - 1, x)) {
        remainingDestinations.add(arrayOf(y - 1, x, map[y][x]))
    }
}

fun isMovable(y: Int, x: Int): Boolean {
    return !(y !in 0..<n || x !in 0..<m || map[y][x] == -3 || 0 <= map[y][x])
}