• 링크 : https://www.acmicpc.net/problem/1697

---

일단 동생을 마지막 위치로 -> graph는 k x k 행렬로(?)

k = 7일때
0 1 2 3 4 5 6 7 

3의 이웃 = 2, 4, 2x3 = [-1, 1, x2] = dx 가 된다

0같은 경우엔 왼쪽이 없는데, 필요없고 if < or >= or < or >= 하면 신경 꺼도 된다

이동할 때마다 cnt += 1

그렇다면 dfs일까 bfs일까
 -> 이웃이 3가지 케이스이니까 bfs인거같고, 이동할 때마다 cnt += 1
 -> 뭔가 안되면 이동 횟수 기록하는 [0,0,0,0 ... ]를 만들고 min()하는 것도 방법임

''' 내가 푼 - 1차 - 답이아님(백업) '''

from collections import deque
x, k = map(int, input().split())
graph = [0 for _ in range(k+1)]

que = deque([x])  # 시작점은 수빈이의 위치 (= x인데 0부터 시작)

dx = [-1, 1, 2]

# BFS는 재귀가 없다 항상 주의해라
while que:
    x = que.popleft()
    cnt += 1
    for i in dx:
        print([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7], 'pop = ', x)
        nx = x + i if i < 2 else x * i
                
        if nx < 0 or k < nx:
            continue
        
        graph[nx] = graph[x] + 1       # (중요) 이게 핵심인데..
        
        if nx == k:
            que.clear()                # = break
            break
        else:
            que.append(nx)
        print(graph, que)
        print()
    print('==========================')
        
print(graph[nx]) 

''' 내가 푼 2차 -> BFS 가 맞았고, 동빈나 / 00 문제랑 같은 결의 문제였다. '''
# 근데 답이 아님

from collections import deque
x, k = map(int, input().split())
graph = [0 for _ in range(k+1)]

#graph[x] = 1      # 시작점의 위치 처음에 방문하니까 +1 해두고!!! (중요)

que = deque([x])  # 시작점은 수빈이의 위치 (= x인데 0부터 시작)

dx = [-1, 1, 2]

# BFS는 재귀가 없다 항상 주의해라
while que:
    x = que.popleft()
    cnt += 1
    for i in dx:
        print([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7], 'pop = ', x)
        nx = x + i if i < 2 else x * i
                
        if nx < 0 or k < nx:
            continue
        
        graph[nx] = graph[x] + 1       # (중요) 이게 핵심인데..
        
        if nx == k:
            que.clear()                # = break (<- 내 코드에서 여기에 print() 추가했어야)
            break
        else:
            que.append(nx)
        print(graph, que)
        print()
    print('==========================')
        
print(graph[nx]) 

---

최단 경로를 도출해내는 방법

• 일단 내가 접근한 방식이 맞았고, BFS도 맞았다
• 다만 내가 생각해내지 못한 것은 "최단경로"이다. (-> 내 솔루션은 최장경로가 될 수밖에 없다)
• 내가 원하는 위치 or 값을 찾으면 바로 break 하자
  

''' 블로그 솔루션 - 내가 접근한게 맞았는데, "최단 경로" 찾는 방법을 몰랐네! '''
from collections import deque

def bfs(x, k, graph):
    que = deque([x])
    dx = [-1, 1, 2]
    
    while que:
        x = que.popleft()
        
        # (중요) 이게 다름 -> 여기서 끝내버렸어야
        # 여기서 끝내도록 전처리한 이유 : 이전 타임(=밑에서) graph[nx]에 graph[x] + 1을 하기 때문
        # 즉, 그때 방문해서 끝나는게 아니고 여기서 찐으로 방문하는 거임
        if x == k:
            print(graph[x])   # (중요) 이렇게 첫 번째로 발견했을 때 바로 출력하고 끝냈어야
            break
            
        for i in dx:
            nx = x + i if i < 2 else x * i
            
            if 0 <= nx <= MAX and graph[nx] == 0:
                graph[nx] = graph[x] + 1          # (중요) 이게 맞았음!
                que.append(nx)                    # (중요) BFS 전부 넣어줘

                
MAX = 10**5                   # (Tip) list out of range 예방용

x, k = map(int, input().split())
graph = [0 for _ in range(MAX + 1)]


bfs(x, k, graph)

. . .

• 그니까 결론은 BFS는 모든 탐색 끝까지 다 하는데
• 이 경우는 BFS로 next node로 이동 계속 진행하다가 pop()한게 내가 찾던 값이야
• 그럼 print() 및 return / break