[BOJ_1697/Python] 숨바꼭질

문제

1697번: 숨바꼭질

1697번: 숨바꼭질

 

---

풀이

from collections import deque


def bfs(start):
    q = deque()
    q.append((start, 0))  # 시작 점, 초(sec)

    visited = set()

    while q:
        x, sec = q.popleft()
        operation = [x - 1, x + 1, x * 2]

        for i in range(3):
            nx = operation[i]

            if 0 <= nx <= 100000 and nx not in visited:
                if nx == K:
                    return sec + 1

                if nx <= K + 1:
                    visited.add(nx)
                    q.append((nx, sec + 1))


# 입력
N, K = map(int, input().split())

# 풀이 & 출력
print(N - K if N >= K else bfs(N))

1. N(수빈이 위치)이 K(동생 위치)보다 큰 값을 가지고 있다면 최소 시간으로 이동할 수 있는 연산이 x - 1 밖에 없기 때문에 단순히 N - K 를 출력한다.

2. N이 K보다 작은 값을 가지고 있다면 최소 시간을 찾기 위해 bfs 를 활용한다. 이때 엄청나게 많은 경우의 수가 발생하기 때문에 시간 초과를 막기 위해 2가지 조건을 덧붙였다.

• 노드 방문 확인(visited) 후 이미 방문한 노드라면 방문하지 않음
• 다음에 방문할 노드가 K + 1 이하일 경우에만 유망한 노드로 판단함 (K + 2 이상의 값에서 -1 을 반복하며 목표값에 도달하는 경우는 없다.)