<백준> 숨바꼭질 3(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%203

[백준]

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

 

문제에 대한 접근만 딱 정해지니까 쉽게 해결했던 문제지만 풀고나서 돌아보니까 좀 아쉬웠던 문제였다.

 

문제를 처음 보고는 DP가 생각났었는데 그냥 반복문으로 하는 건 아닌 거 같았다.

시간에 대한 처리가 나뉘어야하기 때문이다.

그래서 BFS를 사용하기로 했다.

각 움직임에 대해 처리를 해서 모든 경우의 수를 집어넣으면서 돌렸다.

시간을 BFS 함수 내의 변수로 둘까 하다가 사용성을 생각해봤을 때 위치와 함께 같이 있는게 낫다는 생각이 들어서 Pair로 묶었다.

DP 배열은 Int형의 최댓값으로 초기화를 해놨다가 현재 시간이 배열값보다 작다면 변경할 수 있게 했다.

이렇게 하고 제출했더니 통과했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.ArrayDeque
import java.util.StringTokenizer

var n: Int = 0
var k: Int = 0
var dp = Array(100001) { Int.MAX_VALUE }

fun main() = with(System.`in`.bufferedReader()) {
    with(StringTokenizer(readln())) {
        n = nextToken().toInt()
        k = nextToken().toInt()
    }

    bfs()
}

fun bfs() {
    val q = ArrayDeque<Pair<Int, Int>>()
    q.add(Pair(n, 0))
    dp[n] = 0

    while (q.isNotEmpty()) {
        val cur = q.removeFirst()

        if (cur.first - 1 >= 0 && dp[cur.first - 1] > cur.second) {
            dp[cur.first - 1] = cur.second + 1
            q.add(Pair(cur.first - 1, cur.second + 1))
        }

        if (cur.first + 1 <= 100000 && dp[cur.first + 1] > cur.second) {
            dp[cur.first + 1] = cur.second + 1
            q.add(Pair(cur.first + 1, cur.second + 1))
        }

        if (cur.first * 2 <= 100000 && dp[cur.first * 2] > cur.second) {
            dp[cur.first * 2] = cur.second
            q.add(Pair(cur.first * 2, cur.second))
        }
    }

    println(dp[k])
}

 

이렇게 풀고나서 걸린 시간을 보는데 이전에 자바로 풀었던 코드보다 2배가 느리더라

왜 그런지 체크해보니까 자바 코드에서는 현재 위치가 k일 때 BFS를 탈출할 수 있었다.

'왜 이걸 그냥 넘겼을까...' 싶더라

BFS에 대해 확실히 이해하지 못하고 있었음을 알았다.

BFS 상에서 k에 먼저 도착했다면 그게 가장 최단 거리이자 최단 시간이었을 텐데...

그 부분을 수정했더니 20퍼정도 빨라졌다.