[ 백준 1697 ] 숨바꼭질 - Python

문제 보기

이 문제는 bfs 문제이다.

 

수빈이가 3가지 연산을 통해서 동생에게 최대한 빠르게 갈 수 있는 시간을 출력하는 문제이다.

최단 시간과 관련된 문제는 대부분 bfs와 관련이 있는 것 같다.

 

알고리즘 순서는 다음과 같다.

1. 수빈이의 현재 위치를 큐에 담는다.

2. 현재 위치에서 갈 수 있는 위치를 큐에 담는다(현재 위치 + 1, -1, * 2)

3. 2번 과정을 동생의 위치가 나올 때까지 반복적으로 한다.

 

위 알고리즘으로 구현을 하여도 시간 초과 혹은 메모리 초과가 발생할 수도 있다.

방문 여부를 확인하는 visited를 list형으로 했을 때 시간 초과가 발생했으며, 큐에 담는 위치를 제한하지 않으면 메모리 초과가 발생하였다.

 

따라서 방문 여부는 set으로, 큐에 담는 위치는 0 이상 10만 이하의 수로 제한하니까 통과하였다.

---

코드

from collections import deque


def bfs(start, end):
    visited = set()
    if start == end:
        return 0
    else:
        q = deque([start])
        cnt = 1
        while True:
            temp = deque()
            while q:
                val = q.popleft()
                if val - 1 == end or val + 1 == end or val * 2 == end:
                    print(cnt)
                    exit()
                else:
                    if val - 1 >= 0 and val - 1 not in visited:
                        visited.add(val - 1)
                        temp.append(val - 1)

                    if val + 1 < 100001 and val + 1 not in visited:
                        visited.add(val + 1)
                        temp.append(val + 1)

                    if val * 2 < 100001 and val * 2 not in visited:
                        visited.add(val * 2)
                        temp.append(val * 2)
            cnt += 1
            q.extend(temp)


if __name__ == "__main__":

    N, K = map(int, input().split())
    if N > K:  # 뒤로만 가는 경우
        print(N - K)
    else:
        print(bfs(N, K))