[BOJ/백준] 1697. 숨바꼭질 (Python)

🔎 문제

🔗 백준 1697. 숨바꼭질

💡 풀이

일단 dfs는 시간초과가 났던 것으로 기억한다.

bfs로 풀면 되는데 이 문제에서 기억할만한 것들은

📍방문지점 체크

처음에는 Q = deque([(n, count)])같이 큐에 방문 노드와 count변수를 넣어줬었는데

visited가 True인지 False인지만 체크 하지 않고 🔗2178미로탐색처럼 다음 방문지점을 현재 방문지점값에서 +1해주며 방문여부를 확인할 때는 0이 아닌지 보면 된다.

# MAX = 10 ** 5 (문제에서 주어진 조건)
# dist 배열 init
dist = [0] * (MAX + 1)
...
# 방문지점 체크와 동시에 카운팅
dist[nx] = dist[cur] + 1

이렇게 하면 결과값을 별도의 변수 없이 뽑을 수 있다.

그리고 인덱스는 0부터이기 때문에 dist 배열 초기화 시에 문제에서 주어진 MAX에 +1을 꼭 해주어야 한다!

📍for문 적극 활용

for nx in (cur - 1, cur + 1, cur * 2):

처음에 이런 문법이 안떠올라서 별도의 함수를 구현해주었는데 그럴 필요 없다.

그리고 이쯤되면 당연한거지만 bfs는 deque를 써야 한다. 리스트의 pop(0)은 시간복잡도가 O(n)으로 좋지 않다.

📃 소스코드

from collections import deque    
MAX = 10 ** 5

def bfs(n, k):
    Q = deque([n])
    dist = [0] * (MAX + 1)
    
    while Q:
        cur = Q.popleft()
        if cur == k:
            print(dist[cur])
            break
        
        for nx in (cur - 1, cur + 1, cur * 2):
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[cur] + 1
                Q.append(nx)
    
n, k = map(int, input().split())
bfs(n, k)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️