[99클럽 코테 스터디 TIL 7일차 / 백준 1697] 숨바꼭질 (Python)

 

일단 이 문제는 이미 풀어본 문제라 작성했던 코드를 기반으로 TIL을 작성하고자 한다.

사실 6일차 문제도 전에 이미 풀어봤던거였다.. 이게 99클럽 코테의 단점 중 하나인가

그래서 TIL을 작성하고 나는 미들러 보너스 문제를 풀어보려고 한다.

 

일단 로직을 짤때 BFS 탐색 방법을 사용하고 매번 갈 수 있는 방향이 [ x-1, x+1, x*2 ] 라는 것을 염두해두었다.

 

내 코드

from collections import deque

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

queue = deque()

def bfs():
    queue.append(n)
    while queue:
        x = queue.popleft()
        # 위치가 동생의 위치와 같으면 해당 위치까지 가기위한 시간 반환
        if x == k:
            return dist[x]
        # 이동할 수 있는 방향 3가지
        for i in [x-1, x+1, x*2]:
            dx = i
            # 이동할 위치가 범위를 넘지 않고 방문한적 없어야 함
            if 0 <= dx <= 10**5 and not dist[dx]:
                # 해당 위치에 가기까지 시간
                dist[dx] = dist[x] + 1
                queue.append(dx)

dist = [0]*(10**5+1)
print(bfs())

 

1. BFS 탐색 방법으로 언니가 이동할 수 있는 모든 방법, 위치를 구한다.

2. 이동 방향은 [ x-1, x+1, x*2 ] 로 설정한다.

3. 처음으로 동생과 위치가 같아진 경우 해당 위치까지 가는데 걸린 시간 반환

 

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