< BFS > 1697번 숨바꼭질 with 파이썬

 

문제

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

 

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

입력

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

출력

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

정답비율

24.964%

알고리즘 분류

 #그래프이론 #그래프탐색 #너비우선탐색 #BFS

 

from collections import deque

def bfs(x, y):
    count = 0
    queue = deque()
    queue.append((x, count))
    visited = set()
    visited.add(x)
    while queue:
        new, count = queue.popleft()
        if new == y:
            return count
        for next in (new + 1, new - 1, new * 2):
            if 0 <= next < 100001 and next not in visited:
                queue.append((next, count+1))
                visited.add(next)

n, k = map(int, input().split())
print(bfs(n, k))

 

 - 쉬운 문제로 판단하고 가볍게 풀었는데 메모리초과를 2번, 시간초과를 1번이나 내버린 아주 못된 문제이다.

 

 - 메모리초과는 사실 파이썬의 문제도 있겠지만 이런 부분이 공부를 하는 데에 있어서는 크게 도움이 되는 것 같다. 

 

 - 처음에는 bfs함수 내에 next의 조건판단문과 방문체크 없이 무조건 큐에 넣었다. 그랬더니 메모리 초과가 났다.

 

 - next를 100000 이하일 경우에만 넣도록 조건을 주었다. 그리고 방문체크도 필요할 것 같아서 리스트 크기를 100,000으로 준 후 True, False를 넣어서 체크하였다. 또 메모리가 터졌다.

 

 - 이번에는 리스트에 방문한 숫자를 넣는 방식으로 방문체크를 했다. not in 을 사용하여 체크하였다. 이랬더니 시간이 터졌다. 

 

 - 리스트의 in 은 n의 복잡도를 가지기 때문에 아무래도 처음 접근부터 잘못 된 듯 했다. 딕셔너리를 사용해서 상수 복잡도로 내릴 수도 있었지만, set을 사용해보았다. set을 사용하면 리스트와 동일하게 in으로 체크할 수 있지만 시간복잡도는 상수 복잡도이기때문에 코드를 크게 변형시킬 필요가 없다.

 

 - 다행히 set으로 방문체크를 했더니 무사히 통과되었다.

 

 

---

 

참고

 

1697번: 숨바꼭질