백준_1697_숨바꼭질

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

1697번: 숨바꼭질

문제 요약)

수빈이의 현재 위치가 N, 동생의 현재 위치가 K라고 했을 때, N -> K 몇 초 걸리나? (0 <= N, K <= 100,000)

1초당, 걷기 (x - 1) or (x + 1) 이거나 2x 이동 가능하다.

힌트: 5 10 9 18 17 순으로 4초만에 찾을 수 있다.

 

입력)

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

 

출력)

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

 

풀이 포인트)

힌트에 따라 다음과 같이 생각할 수 있다. 

N = 5, K = 17 이라고 할 때,

0초 5

1초 4(-1)  6(+1)  "10(x2)"

2초                        "9(-1)"  11(+1)    20(x2)

3초                          8(-1)   10(+1)  "18(x2)"

4초                                                   "17(-1)"  19(+1)  36(x2)

" " 친 순서대로 풀이 한다.

또 최단거리를 찾는 문제이기 때문에 bfs를 사용한다.

 

풀이)

#파이썬 queue는 deque를 사용해 구현한다.
from colletions import deque #파이썬에 내장된 collections에서 deque를 불러온다.

#함수 정의 전 처리
MAX = 10 ** 5 #최댓값 설정으로 수 제한
dist = [0] * (MAX + 1) #dist 변수 설정 -> 최댓값에 1을 더한 만큼 [0, 0, ... 0] 리스트 생성
n, k = map(int, input().split()) #정수를 입력받을 n, k 변수 설정

#bfs
def bfs(): #def로 bfs함수를 정의한다.
	q = deque() #변수를 deque로 초기화
    q.append(n) #q시작점인 5 추가
    while q: #q가 정수일때 반복
    	x =q.popleft(): #deque() 왼쪽에 있는 수를 빼주는 popleft(). 여기서는 deque에 있는 수빈이의 위치를 x로 꺼낸다.
        if x == k: # 수빈이와 동생 위치가 같아지면
        	print(dist[nx]) #걸린시간 dist[x]를 출력
            break #while문 탈출
        for nx in (x-1, x+1, x*2): #q.append(5)에서 popleft된 x = 5 -> nx - 4, 6, 10
        	if 0 <= nx <= MAX and not dist[nx]: #0 <= 4, 6, 10 <= MAX와 not dist[4, 6, 10]이 거짓이면 (dist[nx] = 0) 조건이 언제나 거짓인 if "not" dist[nx] 만족한다
            dist[nx] = dist[x] + 1 #dist[4, 6, 10] = dist[5] + 1 = 0 + 1 = 1
            q.append(nx) #q = deque([4, 6, 10])
             # for문 반복 (힌트 5 - 10 - 9 - 18 - 17)
        	 # popleft x = 10, nx = 9, 11, 20 / dist[9, 11, 20] = dist[10] + 1 = 1 + 1 = 2
        	 # popleft x = 9, nx = 8, 10, 18 / dist[8, 10, 18] = dist[9] + 1 = 2 + 1 = 3
        	 # popleft x = 18, nx = 17, 19, 36 / dist[17, 19, 36] = dist[18] + 1 = 3 + 1 = 4
        	 # ~> q = deque([17, 19, 36])에서 x = q.popleft() -> x = 17, q = deque([19, 36])
        	 # ~> if문 x == k -> dist[17] ~> 4출력
            
bfs() #def로 정의한 bfs함수 실행, 출력