[백준] 1697 숨바꼭질 (파이썬/python)

🎈문제

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

 

🎁어떤 알고리즘?

1. 1차원에서의 bfs

2. 2차원 리스트에서 상하좌우의 움직임을 보여준 기존의 문제들과 달리 이 문제에서는 1차원에서 [-1,+1,*2]만큼의 x좌표 움직임을 보여준다고 이해하면 될 것 같다.

 

 

💻코드

from collections import deque

def bfs(x):
    deq = deque()
    deq.append(x)

    while deq:
        x = deq.popleft()

        if x == k:
            print(graph[x])
            break

        for i in [x-1,x+1,x*2]:
            nx = i
            if nx < 0 or nx > (100001)-1:
                continue
            if graph[nx] == 0:
                graph[nx] = graph[x] + 1
                deq.append(nx)
                # print('graph:',graph)
                # print('deq:',deq)
    return

n,k = map(int,input().split())  #  n:수빈 위치, k:동생 위치
#graph
graph = [0 for i in range(100001)]

bfs(n)

🎄코드 설명

 문제의 예시를 bfs로 풀어내는 과정을 살짝 보여주면

1. [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...] 5번째 idx를 bfs에 넣고 돌리면

2. [0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,...] 이렇게 5번째 idx(index)를 기준으로 4번째, 6번째, 10번째 idx가 1로 바뀌는 것을 볼 수 있다. 그리고 각각 4번째 6번째 10번째 idx는 큐에 들어가 다음에 -1,1,2배 각각 한번씩 모두 이동한다.

3. [0,0,0,2,1,2,1,2,2,2,1,2,2,0,0,0,0,0,0,0,2,...]

4. [0,0,3,2,1,2,1,2,2,2,1,2,2,3,3,0,3,0,3,3,2,...]

5. [0,4,3,2,1,2,1,2,2,2,1,2,2,3,3,4,3,4,3,3,2,...] 이와같이 반복하다보면 결국 17번째 idx에 가장 최적의 횟수가 입력된다.

 

bfs를 떠올렸다면, 다음으로 생각해볼 만한 것이 'graph의 범위를 어떻게 할 것인지'이다. [뒤로 한 칸, 앞으로 한 칸, 앞으로 두 배] 이렇게 세 움직임만을 보여준다면 앞으로 가기는 쉬워도 뒤로 가기는 어려우므로 동생을 지나친 다음 -1을 여러번 해서 올 바엔 최대한 미리 -1을 이용해 2배 만큼씩 앞으로 오겠구나 싶었다. 따라서 동생의 최대 범위 만큼 100001을 설정해줬다.

 

if x==k: 를 이용해서 탈출하는 문장이 저 위치에 있는 이유는 같은 값을 넣었을 때 0의 값을 뱉어내기 위해서이다.

ex) 5 5 를 입력으로 받으면 0을 출력해야한다.