[BOJ-1697] 숨바꼭질 (BFS)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 

5 17

예제 출력 

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

[접근]

구하고자 하는 것: 최소 시간. 한번 이동시 1초이므로 최소 이동 횟수를 세면된다.

최단 거리 문제이므로 bfs 알고리즘을 사용했고, 위치와 이동 횟수를 함께 기록했다

 

1. 현재 위치 N 의 인접노드 N-1, N+1, 2*N 를 순차적으로 방문한다.

2. 방문하는 노드와 이동 횟수를 튜플로 큐에 삽입한다.

3. 다음 노드 O 또한 O-1, O+1, 2*O 을 인접노드로 갖는다 

4. 만약 방문한 노드가 K(동생 위치) 와 같은 경우 횟수를 반환하고 종료한다.

 

처음 코드

from collections import deque

n, k = map(int,input().split())
visited =[n] #갔던 위치
q= deque([(n,0)])

while q:
    v, t = q.popleft() 				#위치값(val)과 이동횟수(turn)
    #print("({},{})".format(v,t))
    if v == k:
        print(t)
        break
    a = [2*v,v+1,v-1]
    for way in a:
        if way in visited or way<0 or way>100000:
            continue
        else:
            q.append((way,t+1))
            visited.append(way)

 

처음엔 n==k 인 경우를 놓쳐서 헤맸다.

이렇게 실행하면 IDE에서는 실행이 잘 된다.

그런데 백준에서는 시간초과 오류가 뜬다. (속상)

해결 방법을 몰라 도움을 요청했는데 지나가던 고마운 분께서 꿀팁을 알려주셨다

 

* visited 를 [] 리스트 형태로 해서 in 연산이 오래걸린다! Set() 타입이 빠르다!

15번 줄 방문 노드를 기록하는 리스트에 현재 위치가 있나없나 확인하는 부분에서

if way in visited: 를 수행할 때 오래걸린다는 말씀이었다... set 으로 하면 빠르다는 것을 처음알았다.

 

그리하여 최종 수정 코드

from collections import deque

n, k = map(int,input().split())
visited =set([n]) 				#수정한 부분
q= deque([(n,0)])

while q:
    v, t = q.popleft() 			#위치값(val)과 이동횟수(turn)
    #print("({},{})".format(v,t))
    if v == k:
        print(t)
        break
    a = [2*v,v+1,v-1]
    for way in a:
        if way in visited or way<0 or way>100000:
            continue
        else:
            q.append((way,t+1))
            visited.add(way)

 

188ms 로 정답 판정을 받았다. 

시간복잡도가 중요한 코딩테스트에서 유용한 꿀팁을 얻은거같아 기쁘다 😀