아이디어:
앞선 A->B 문제와 비슷한 방식으로 그래프를 구현하여 풀 수 있을 것 같다. 대신 이번 문제는 무조건 BFS로 풀어야 한다.
생각해야 할 조건이 많아서 예상외로 까다로웠다.
처음에 그냥 제출하니 메모리 초과가 났고.. 그래서 한 번 만든 수를 다시 만들지 않도록 visit 배열을 추가했다. 예를 들면 *2를 하여 이미 한번의 경로만을 사용하여 만든 수를 +1 두번을 사용하여 같은 수를 다시 만드는 것은 불필요하기 때문이다.
그리고 나니 인덱스에러가 생겼는데, n[0]의 범위가 주어진 좌표의 범위를 넘어서는 경우가 발생할 수 있기 때문이었다. 따라서 조건에 그것도 추가했더니 통과했다.
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
q = deque()
q.append([N, 0])
#메모리 초과를 줄이기 위해.. 쓸데없는 연산 제거.
visit = [False]*100001
while(q):
n = q.popleft()
if (n[0]==K):
print(n[1])
sys.exit(0)
if (n[0]<=100000 and n[0]>=0 and visit[n[0]]==False):
visit[n[0]]=True
q.append([n[0]*2, n[1]+1])
q.append([n[0]-1, n[1]+1])
q.append([n[0]+1, n[1]+1])
'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글
BOJ 2606번: 바이러스 (0) | 2021.02.08 |
---|---|
5829번: Luxury River Cruise (0) | 2021.02.08 |
BOJ 19538번: 루머 (0) | 2021.02.07 |
BOJ 16953번: A → B (0) | 2021.02.06 |
BOJ 1260번: DFS와 BFS (0) | 2021.02.06 |