[백준 1697번] 숨바꼭질 - 파이썬

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

💡문제 분석 요약

수빈이는 1초에 X-1, X+1, 2*X로 이동할 수 있다. 동생의 위치로 이동하기까지 걸리는 가장 작은 시간을 구하라
 

💡알고리즘 설계

DFS 문제로 큐를 사용한다.
현재 수빈이의 위치를 큐에 넣고, 그 위치에서 X-1, X+1, 2*X로 이동시킨 후 visted[]에 1을 하나씩 더해 이동에 걸린 시간을 저장한다.

1. 빈 큐에 현재 수빈이의 위치를 추가
2. 큐가 빌 때 까지, 노드를 하나 꺼낸다.
   1. 해당 노드의 x-1, x+1,2*x가 범위 내이고, x-1, x+1, 2*x이 방문한 적이 없는 노드 경우,
   2. 큐에 x-1, x+1, 2*x를 추가하고, 현재 노드를 이전 노드의 visited에 1을 더한 값으로 설정한다.

갈 수 있는 위치가 0<=x<=100000으로 한계가 있기 떄문에, visited[] 배열도 그 크기만큼 미리 만들었고, 방문했는지 판별할 때도 x가 이 위치를 벗어나는지 체크해줬다.

 

💡코드

from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())

visited = [0]*(100001)

def bfs (node, visited, k):
    queue = deque([node])
    
    while queue:
        x = queue.popleft()
        if x==k:
            print(visited[k])
            return
        for i in (x-1, x+1, x*2):
            if 0<=i<=100000 and visited[i]==0:
                queue.append(i)
                visited[i] = visited[x]+1

bfs(N, visited, K)

💡시간복잡도

while 안에 for문이 들어가서 n^2인가 헷갈리긴 하지만..
visitted[]를 이용해 한번 방문한 노드는 방문하지 않으므로 O(n)이 걸린다고 생각했다.
 

💡 느낀점 or 기억할 정보

deque는 처음 써보기도 하고, list로는 구현할 수 없을까? 싶었는데 list의 pop(0)는 시간복잡도가 O(n)이 걸린다고 한다.
처음에는 최단거리를 구하기 위해 dp를 이용할까 생각했었는데 BFS를 공부해보고 싶어서 BFS를 풀었다. 훨씬 코드가 간결해서 좋은 것 같다. dp로도 충분히 구현할 수 있는 문제같다