[백준] 1697번 숨바꼭질 - python

 

<문제>

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

1697번: 숨바꼭질

<시간 복잡도>

시간 복잡도는 어 음... 잘 모르겠다. 아는 건 우선 deque 라이브러리는 탐색을 수행할때 O(N)을 잡아먹는 빠른 라이브러리하는건 안다. 

<코드>

from collections import deque

n,k = map(int,input().split())
visited = [False] * 100001
dx = [-1, 1 , 2]

def bfs(n,k):
    end = k
    q = deque()
    q.append([n,0])

    visited[n] = True
    while q:
        x, t = q.popleft()

        if x == end:
            return t

        for i in range(3):
            if dx[i] == 2:
                nx = dx[i]*x
            else:
                nx = x + dx[i]
            if 0 <= nx <=100000 and not visited[nx] :
                visited[nx] = True
                q.append([nx,t+1])



print(bfs(n,k))

<해설>

이 문제에서 핵심은 시간을 세는 방법이다.

이외의 풀이에서 BFS의 기본이니 꼭 알아두자 방문에 VISITED 체크와 움직이는 방향 결정 dx 와 같은 방법을 사용하면된다.

 

앞에 말한 이 문제의 핵심은 시간을 세는 방법인데 처음에는 그냥 count라 하고 for i in range(3) 이 끝나고 밖에 나올때

count +=1 의 방식으로 접근했지만 이렇게 접근을 하게 될때 시간에 대한 count 의 문제가 발생한다. 

따라서 nx 가 방문 가능한 지역일 때 같이 t 라는 시간을 배열에 deque 에 넣어주게 되면서 문제를 해결 할 수 있었다. 

끝