[백준] 1697(숨바꼭질) 파이썬

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

풀이 및 리뷰

전형적인 BFS 문제이므로 풀이는 크게 어렵지 않다. 주의할 점은 시간 초과다. 이에 대해 세 가지 정도 얘기할 것이 있다.

 

먼저 deque에 관한 것이다. 처음 파이썬에서 큐를 사용할 땐 리스트를 사용하여 pop(0) 함수로 큐를 사용했다. 하지만 이는 pop할 때 시간복잡도가 O(n) 이므로 시간초과가 생길 수 있다. 파이썬에서 제공하는 deque은 pop할 때 시간복잡도가 O(1)이다. 따라서 이를 사용하면 시간을 단축할 수 있다.

from collection import deqeue
q = deque()
q.append('') # 큐에 삽입
a.popleft() # 가장 먼저 들어온 것을 pop

 

다음은 범위에 관한 것이다. 다음 지점의 조건을 검사할때 0~100,000의 범위 조건도 검사 해야한다. 사실 이 부분은 납득이 잘 되지 않는다. 문제에선 현재 있을 수 있는 곳이 0~100,000 이라고 했지 점이 0~100,000이라고 명시하지 않았기 때문이다. 하지만 해당 조건이 없다면 문제를 아마도 풀 수 없다. 문제를 많이 풀다 보면 어떠한 조건이 당연히 필요한 것이라 생각하고 푸는 것일까..

 

마지막은 조건문에서 in 연산자에 관한 것이다. 이전까지 BFS 문제를 풀 때 방문한 노드를 검사하기 위해 리스트 V를 사용하여 방문한 노드는 append했다. 검사할 때는 이 V에 해당 노드가 'in' 인지 확인했는데, in 연산은 시간복잡도가 O(n)이라 이 문제에서 시간 초과를 발생시켰다. 때문에 V를 노드 전체 수의 배열로 만들고 방문하지 않은 노드는 0으로 방문한 노드는 1로 두는 방법으로 방문한 노드를 검사했다.

코드

from collections import deque
def bfs(s, e):
    time = 0
    q, v = deque(), [0]*100001 # queue, visited
    q.append(s)
    v[s] = 1
    while q:
        # 현재 큐에 있는 모든 요소 검사
        for _ in range(len(q)):
            curr = q.popleft()
            # 목적지에 도달하면
            if curr == e:
                return time
            # 세 가지 방법을 검사
            for next in (curr+1, curr-1, curr*2):
                # 범위를 넘지 않고 next 를 방문하지 않았다면
                if 0<=next<=100000 and v[next]==0:
                    q.append(next)
                    v[next] = 1
        time += 1
#입력
N, K = map(int, input().split())
print(bfs(N, K))

 

1697번: 숨바꼭질