[Python] 백준 12851번: 숨바꼭질 2(시간복잡도 2등)

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

12851번: 숨바꼭질 2

 

import sys
input = sys.stdin.readline


def getMinTimeAndCaseCount(N, K):
    if N >= K:
        return N-K, 1

    curTime = 0
    todo = [N]
    minTimes = [float('inf')]*100001
    minTimes[N] = 0

    while todo:
        print(todo)
        nextTodo = []
        caseCount = 0
        curTime += 1

        for n in todo:
            if n > K:
                next = [n-1]
            elif n >= 2 and (K / n) % 2 == 0 and K != 0:
                next = [n*2]
            else:
                next = [n-1, n+1, n*2]

            for i in next:
                # 범위 벗어날 경우
                if i < 0 or i > 100000:
                    continue

                # 일치 시 카운트
                if i == K:
                    caseCount += 1

                # 시간 체크하여 방문
                if minTimes[i] >= curTime:
                    minTimes[i] = curTime
                    nextTodo.append(i)

        # 1번이라도 카운트 되었을 시
        if caseCount > 0:
            return curTime, caseCount

        todo = nextTodo


if __name__ == '__main__':
    N, K = map(int, input().split())

    minTime, caseCount = getMinTimeAndCaseCount(N, K)
    print(minTime)
    print(caseCount)

 

BFS로 문제를 풀었다.

 

먼저 getMinTimeAndCaseCount() 함수 첫부분을 보자. 1 1과 같은 입력에 대한 처리를 하고자 N == K로 조건을 달아도 되지만, 저렇게 하면 해당 예외 처리도 될 뿐더러, 100 0과 같은 케이스도 바로 처리된다. 덧붙여 설명하자면, 100 0의 경우에는 -1씩 100번 하는 경우밖에 없다.

 

다음은 본격적인 BFS이다. todo, nextTodo를 이용하여 시간을 1씩 증가시키면서 작업을 진행시켰다. 이에 따라 curTime 변수도 1씩 증가하는데, 사실 curTime에서 접근해도 현재 시간을 얻을 수 있지만 인덱싱 때문에 O(N)의 작업을 수행하게 되므로 curTime을 사용하는 편이 낫다.

 

todo에 대해서 for문을 돌게 된다. 이 때 todo의 각 원소는 n인데, n에서 파생되는(보통, n-1, n+1, n*2) 위치들을 next에 담는다. 다만 여기에 조건이 있는데 이것은 효율을 위한 것이다. else문에 대한 next가 가장 일반적인 경우이다.

첫번째 조건문을 설명하자면, 가령 n이 100인데 K가 70일 경우 다음에 굳이 101과 200을 고려하지 않아도 된다는 것이다.

두번째 조건문은 쉽게 말하면 K가 n의 배수일 때이다. n이 7이고 K가 28인 경우가 그 예시이다. 이 때는 2를 곱하는 경우가 무조건 빠르므로 이렇게 하는 것이다.

 

이렇게 next가 완성되었으면 next에 대해 for문을 돌아준다.

처음으로 범위 체크를 해주고, out of range일 경우 continue로 통과해준다.

다음으로 i==K일 때 caseCount라는 것을 증가시켜준다. 이것은 출력값으로, todo에 대해 반복문을 돌면서 1번이라도 증가되었다는 것은, K를 방문했다는 것을 의미한다.

그리고 minTimes를 이용해 해당 위치에 처음 접근하였거나(minTimes는 inf로 초기화된다.), 현재 시간에서 이전에 방문이 있었을 경우, minTime값을 현재 시간으로 넣어주고, 다음에 돌게 될 nextTodo에 인덱스 값을 추가한다.

 

이렇게 특정 시간에 대한 반복문(todo)가 끝나면, caseCount의 값이 증가되었을 경우(즉, K에 접근했을 경우), 현재 시간과 경우의 수를 리턴해준다. 그렇지 않을 경우는 다음 탐색을 진행하기 위해, 인덱스값이 추가되어있는 nextTodo를 todo에 넣어준다.

 

이 풀이에서 minTimes가 매우 중요한 역할을 해준다. 모든 경우의 수를 알아야하므로, isVisited를 쓰지 않았으며, minTimes의 값이 같을 경우에도 i를 추가해주었다는 것이 중요하다. 아래 예시가 이를 설명해준다.

 

입력:

1 3

출력:

2

2

1에서 nextTodo에 2를 2번을 담아줘야 올바른 값이 나온다.

 

 

여담으로 골드5가 맞나 싶었다.