[백준 12851] 숨바꼭질 2 파이썬

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

12851번: 숨바꼭질 2

from collections import deque

N,K = map(int,input().split())
MAX = 100000+1

def bfs(N,K):
    visited = [0]*(MAX)
    visited[N] = 1
    time = 0
    min_time = MAX
    cnt= 0
    q = deque([[N,time]])
    while q:
            x,t = q.popleft()
            # print("x,t,cnt : ",x,t,cnt)

            visited[x] = 1

            if t > min_time:
                continue

            if x==K:
                if min_time == t:
                    cnt+=1
                elif min_time == MAX:
                    min_time = t
                    cnt+=1
            else:
                for nx in [x-1,x+1,2*x]:
                    if 0> nx or nx>=MAX:
                        continue
                    if visited[nx]:
                        continue
                    q.append([nx,t+1])

    return min_time,cnt

if N >= K:
    print(N-K)
    print(1)
else:
    min_time, ways =bfs(N,K)
    print(min_time)
    print(ways)
    

풀이

방문한 곳을 2번이상 방문하지 않고 최단시간내에 도착지까지 가야하기 때문에 BFS 로 푼다.

이해가 안가면 아래 그림을 보자

그래프가 3진트리 구조라고 생각하자. 자식노드들은 부모노드의 +1,-1, *2로 구성되어 있는 것이다.

예를들어 2로 시작한다면

 

2 (0단계) -> 1,3,4(1단계) -> 0,2,2,2,4,6,3,5,8 (2단계) -> ...

 

이런식으로 그래프가 만들어지는 것이다.

여기서 방문한 것들은 제외하면서 쭉 목적지를 찾을 때까지 진행하면 bfs 이다.

 

여기서 걸리는 최소 시간은 K를 N단계에서 찾았을 때 최소시간이 곧 N이다.

경로의 방법의 수는 N단계에서 찾았을 때 N단계에 있는 노드들 중 K의 수이다.

 

머리속으로 여기까지 생각하고 구현을 하였는데 구현에서 헷갈렸다.

항상 visited처리를 q에 push하면서 처리했는데 여기서는 pop할 때 visited를 처리해 줌으로서

N단계에 있는 모든 노드를 탐색할 수 있었다.

 

시간복잡도

N을 모두 탐색하니 O(N) 이다.