[백준] 1697번 : 숨바꼭질

 

 

 

 

 

 

 

접근법 

- 처음에는 2중 배열로 바꿔서 계산을 해야 하나 고민했는데 그럴 필요가 없음을 깨달았다. (2중 배열로 바꾸면 배열의 사이즈가 계속 달라지기 때문에 불가능)

 

- 배열을 100001의 크기로 만들고 visit[5](출발지)의 값을 1로 설정한다.

 

- queue는 deque를 import하여 만들어 주고 queue에 출발지 값(= 5)을 넣는다.

 

- 평범한 BFS처럼 queue에서 값을 하나씩 빼가면서 진행한다.

 

- val + 1이 배열의 범위를 넘지 않고, 방문한 적이 없다면 visit[val + 1]을 visit[val] + 1의 값을 넣어준다.

 

- 그 후 val + 1에서부터 다시 탐색을 하기 위해 queue에 val + 1을 넣어준다.

 

- val - 1과 val * 2도 같은 방법으로 탐색을 한다.

 

- visit[K] - 1을 출력해준다.(visit[N]의 값이 1이었기 때문에 - 1을 해줘야 함.)

 

 

 

 

 

 

 

풀이

from collections import deque

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

visit = [0 for _ in range(100001)]
visit[N] = 1

queue = deque()
queue.append(N)

while queue :
    val = queue.popleft()
    if 0 <= val + 1 < 100001 and visit[val + 1] == 0 :
        visit[val + 1] = visit[val] + 1
        queue.append(val + 1)
    if 0 <= val - 1 < 100001 and visit[val - 1] == 0 :
        visit[val - 1] = visit[val] + 1
        queue.append(val - 1)
    if 0 <= val * 2 < 100001 and visit[val * 2] == 0 :
        visit[val * 2] = visit[val] + 1
        queue.append(val * 2)

print(visit[K] - 1)

 

 

 

 

 

 

 

결과