[백준]_1697번 : 숨바꼭질(파이썬)

1697번: 숨바꼭질

728x90

 

리스트 2개를 동시에 나눠서 관찰해야 되는 문제였다. 한 개는 이동 횟수를 추적하는 리스트이고 다른 하나는 너비 우선 탐색에 이용될 deque 배열이다. 

 

전략

먼저 n, k를 입력 받을 것이다.

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

n, k = map(int, input().split())

 

이제부터 설명의 편의를 위해 n대신 백준에 예시로 나온 대로 5라고 지칭하겠다. 또한 위에서 말했듯이 5에서부터 시작된 이동 횟수를 추적하는 리스트(repo)와 5에서부터 시작될 너비 우선 탐색 리스트(q)를 만들어줘야 한다.

# n에서 next_location까지 가려면 몇 초가 필요한지 저장하는 리스트
repo = [0] * 100001
q = deque([])
q.append(n)

 

이제부터가 본론이다. 17이 q에 존재할때 까지 아래의 과정들을 반복(while 1)하면 된다.

 

5를 q에서 popleft 해서 inspect에 대입해 준다. 즉 5를 갖고 탐색을 검사(inspect)할 것이다.

while 1:
    inspect = q.popleft()

만약 inspect와 k가 같다면 repo[inspect]를 출력하고 반복문을 탈출한다.

    if inspect == k:
        print(repo[inspect])
        break

같지 않다면 inspect-1, inspect+1, inspect*2를 대상으로 너비 탐색을 한다. 따라서 q리스트에 원소들을 추가하는 것이다. 이때 위 3개의 숫자들은 next_location이라고 명명하자.

    for next_location in (inspect - 1, inspect + 1, inspect * 2):

단 이때 next_location이 q에 추가됨과 동시에 '이동 횟수'로 인정받기 위해서는 next_location은 0 이상 100000 이하, 기존에 방문했던 기록이 없어야 한다. 즉 아래의 조건문을 만족해야 한다.

        if 0 <= next_location <= 100000 and not repo[next_location]:
            repo[next_location] = repo[inspect] + 1
            q.append(next_location)

최종 코드

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

n,k=map(int, input().split())
repo=[0]*100001

q=deque([])
q.append(n)
while 1:
    inspect=q.popleft()
    if inspect==k:
        print(repo[inspect])
        break
    for next_location in (inspect-1, inspect+1, inspect*2):
        if 0<=next_location<=100000 and not repo[next_location]:
            repo[next_location]=repo[inspect]+1
            q.append(next_location)

여기서 들 수 있는 의문은 17이 경로에 따라 여러번 존재할 수 있는데 어느 경로가 최소 이동 경로인지 아느냐이다. 하지만 걱정할 필요가 없다! inspect==k를 가장 처음 만족하는 횟수(repo [inspect])가 무조건 최소 이동 경로이기 때문이다.