[백준 1697] 파이썬 - 숨바꼭질

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

1764번: 듣보잡

 

# 조건

• 수빈이는 현재 점 N(0<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있다.
• 걷을 때 -> 1초 후에 X-1 또는 X+1
• 순간이동 -> 1초 후 2 * X
• 가장 빨리 동생을 찾을 수 있는 시간을 구하라

 

# 접근 방법

 

• 시작 위치부터 끝 점까지 가는 BFS를 이용하여 가까운 곳부터 탐색을 계속 해주면 될 것 같다.
• 기본 시간을 1로 설정한 후 시작 위치의 왼쪽은 전부 +1을 해준다
• 이후 오른쪽으로 가며 k+1과 k * 2 위치의 값을 +1 씩 해주면 될 것 같다.
• 방문 기록을 남겨주는 이유 -> 이미 방문된 곳이라면 x2를 통해 더 최소의 횟수로 갔을 것이기 때문이다.
• 이동하며 목표지점에 도착했다면 종료 후 출력

 

# 다른분 코드 - dfs + 커팅

• 시작 지점이 아닌 도착 지점을 바꿔가며 탐색 해주었다.
• 동생이 X에서 X/2로 이동하는 건 X가 짝수일 때만 가능하기 때문

def find(n, k):
    if n >= k:
        return n - k
    elif k == 1:
        return 1
	# 홀수인경우 도착지점+1, 도착지점 -1만 탐색하며 +1 해준다.
    elif k % 2:
        return min (find(n, k + 1), find(n, k - 1)) +1  
    # 짝수인 경우 시작점-도착점, k//2+1 중 최소값으로 갱신해준다.
    # 또한 k//2 로 이동하여 출발점까지 고고   
    else:
        return min (k - n, find(n, k // 2) + 1)

print(find(*map(int, input().split())))

 

# my 코드 - bfs 이용

from collections import deque

# 수빈이 위치, 동생의 위치
N, M = map(int, input().split())

# 각 위치의 시간을 최댓값 +1 로 해준다.
loca = [0] * 100001


q = deque()
q.append(N)
# bfs 이용
while q:
    # 시작위치에서 오른쪽으로 갈 수 있는 곳을 +1 씩 해주며 전체 거리를 채워준다.
    k = q.popleft()
    # 현재위치 - 도착위치가 같아진 경우 종료
    if k == M:
        print(loca[M])
        break
    for i in (k-1, k+1, k*2):
        # 방문하지 않았고 범위 내라면 -> 방문한 곳이라면 *2로 더 최솟값으로 갔을 것이니까
        if 0<=i<=100000 and loca[i] == 0:
            loca[i] = loca[k] + 1
            q.append(i)

 

• 전형적인 bfs 문제라고 보인다.
• 델타탐색이 아니더라도, 반복문의 iterable한 값을 잘 설정해주는 것이 중요한 듯!