[Algorithm] 백준_1697번: 숨바꼭질

오늘의 예비문제는 🚀 백준 1697 숨바꼭질 이다.

사실 숨바꼭질3이 오늘의 문제인데, 이 스리즈물의 일번부터 뭐였는지 기억이 안나서 다시 풀었다.

테스트케이스 이해하기

수빈이랑 동생이랑 숨바꼭질을 해서, 수빈이가 찾으러 가는 것이다.

이동할 수 있는 방법은 +1, -1, *2 방법이 있고 이동할때 마다 1초씩 흐른다.

가장 빠른 시간을 출력하면 성공!

알고리즘

BFS로 문제를 풀어야 한다.

1. 방문했는지 확인하는 check, 각각 거리가 얼마인지 저장하는 dist를 선언한다.

2. deque를 이용해서 수빈이의 위치를 넣고, while문을 시작한다.

3. 세가지 경우로 나눠서 범위를 확인하고, +1, -1, *2 씩 이동했을 경우를 생각해서 check랑 dist를 채운다.

4. 현재 위치가 수빈이 동생 위치이면 프린트 하고 break 해서 탈출!

   
   

   
   

정답코드

from collections import deque
max=200000
a,b = map(int,input().split())
check=[False]*max
dist=[0]*max

q = deque()
q.append(a)
check[a] = True

while q:
    now = q.popleft()
    if now ==b:
        print(dist[b])
    if -1< now +1 < max:
        if not check[now+1]:
            q.append(now+1)
            check[now+1] = True
            dist[now+1] = dist[now]+1

    if -1< now-1 < max:
        if not check[now - 1]:
            q.append(now - 1)
            check[now - 1] = True
            dist[now - 1] = dist[now] + 1

    if -1< now*2 < max:
        if not check[now * 2]:
            q.append(now * 2)
            check[now * 2] = True
            dist[now * 2] = dist[now] + 1

정답코드2

파이썬일 경우 이런 방식으로 길이를 줄일 수도 있다..! 우왕✨

from collections import deque
max=200000
a,b = map(int,input().split())
check=[False]*max
dist=[0]*max

q = deque()
q.append(a)
check[a] = True

while q:
    now = q.popleft()
    if now ==b:
        print(dist[b])
        break
    for nxt in [now+1, now-1, now*2]:
        if -1<nxt<max and not check[nxt]:
            q.append(nxt)
            check[nxt] = True
            dist[nxt] = dist[now]+1

🚀Reference: 백준 1697 숨바꼭질