[BOJ 1687] 숨바꼭질

Breadth First Search

[BOJ 1687] 숨바꼭질

문제

구조화

• 현재 노드 n, 목표 노드 K 정의
• 최단 거리 문제
  • 혹은 최소 연산 횟수로 도달가능한 Case를 찾는 문제
• 움직일 수 있는 1D Vecotr 공간 생성
• 움직일 수 있는 경우는 3가지
  • n+1
  • n-1
  • 2*n
• 위의 공간에서 현재의 노드를 기준으로 3가지 진행방향에 BFS 실행
  • 만약 방문한 지점이라면 pass
  • 움직일 수 없는 좌표라면 pass
    • 음수
    • 최대 공간인 10만보다 벗어난 좌표
• 1D Vector공간에서 위의 rule에 따라 움직이되, 지나온 좌표 공간에는 +1을 가산하며 몇 초가 흘렀는지 입력
• 만약 목표지점에 도달한 case라면 ans 리스트에 추가
• 이 중 최소값을 출력

예제 시각화

해답

from collections import deque
import sys
input = sys.stdin.readline
n,k = map(int, input().split()) # n은 start, k는 목표 지점
data = [0 for i in range(100001)] # 최대 10만개
a=deque([n]) # start 지점 큐에 추가
ans=[]
def bfs(): 
    while len(a):
        node = a.popleft() 
        if node==k: # 만약 노드의 값이 목표 지점이라면
            ans.append(data[node]) # 정답에 추가
            break
        for nxt in (node-1, node+1, node*2): # 움직일 수 있는 방향은 총 3가지
            if nxt >= 0 and nxt <= len(data)-1: # 이동 가능 영역인 경우
                if data[nxt]==0: # 아직 방문하지 않았다면
                    data[nxt] = data[node]+1 # 1초가 지났음을 추가
                    a.append(nxt) 
bfs()
print(min(ans))