[Python] 백준 12851번 문제, 숨바꼭질 2

<문제 링크>

 

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

12851번: 숨바꼭질 2

 

---

<풀이>

 

수빈이가 동생과 숨바꼭질 하고 있는데 수빈이가 동생을 찾는 가장 빠른 시간이 몇 초 후이며, 가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하는 문제이다.

수빈이가 X(0 ≤ X ≤ 100,000)에 있다고 가정 했을 때, 1초에 { X-1, X+1, 2X }으로 이동할 수 있다. 이렇게 몇 초후에 동생이 있는 K(0 ≤ K ≤ 100,000)에 도달하는지 구하면 된다.

 

def bfs(N, K):
    time = 0
    que = [N]
    new_que = []

    while True:
        if que.count(K) > 0:
            count = que.count(K)
            break

        time += 1
        while que:
            now = que.pop(0)
            visited[now] = True

            if now-1 >= 0:
                if not visited[now-1]:
                    new_que.append(now-1)
            if now+1 <= 100000:
                if not visited[now+1]:
                    new_que.append(now+1)
            if now*2 <= 100000:
                if not visited[now*2]:
                    new_que.append(now*2)

        que = new_que
        new_que = []

    return time, count


if __name__ == "__main__":
    N, K = map(int, input().split())
    visited = [False] * 100001

    time, count = bfs(N, K)

    print(time)
    print(count)

최소 0에서 최대 100,000까지이기 때문에 방문 여부를 판단하는 visited[]를 100,001 크기로 False로 초기화해준다.

bfs()가 중요한 logic인데 자세히 보면 무한 반복 while문 아래에 탐색 순서가 담긴 que만큼 반복하는 while문이 있는 걸 볼 수 있다. 동생을 못 찾는 경우는 없기 때문에 무한 루프에 빠질 일이 없어 무한 반복문 while 안에 que만큼 BFS를 수행하도록 했다.

어쨋든 BFS 탐색이 끝나면 탐색 결과가 담긴 new_que를 다시 que로 초기화해주고 if문에서 que에 K가 1 이상 포함되어 있으면 반복문을 완전 종료하고 que.count(K)를 통해 같은 time에 동일한 방법이 몇 가지가 있는지 return 해준다.

K가 1이상 포함되어 있지 않다면, 탐색이 수행되니깐 time+1해주고 현재 탐색 순서 que에 담긴 모든 요소에 대해 1초에 할 수 있는 Action을 취해 한 번도 방문하지 않았고 X의 범위에 맞다면 new_que에다가 append() 해준다.