문제 이해
문제만 보면 되게 간단해보이는 문제이다! 하지만 정답률이 25%라서 조금 떨면서 시작했다!
하지만 풀면서 느낀점은 그렇게 어려운 문제는 아니라는 것. BFS문제를 조금이라도 풀어봤다면 쉽게 생각할 수 있었다.
문제 접근
우선 이 문제를 보고 x-1, x+1, 2x 를 모두 넣어서 모든 경우의 수를 확인하고 가장 먼저 K에 도달한 값을 출력하도록 해야겠다고 생각했다.
또한 시간을 계산하는 방법도 생각해주어야 했다.
나는 시간계산을 queue에 직접 시간을 넣어서 다음 순서로 전달하는 방식을 택했다.
하지만 문제 풀이 후에 다른 분의 코드도 확인해보니 배열을 설정해서 시간을 1씩 더해주면서 진행하는 방법도 있었는데 그 방법이 좀 더 직관적이었던 것 같다.
따라서 다음번에 이러한 시간체크 문제가 나오면 적용해보도록 하겠다.
문제 풀이
문제에서 주어진 최대 범위가 100000이었기 때문에 상수로 선언해준다.
또한 queue에 중복으로 들어가는 값이 있지 않도록 visited라는 배열을 선언하여 방문표시를 해준다!
BFS에서는 종료조건으로 n==K로 넣고 이 때의 cnt를 출력함으로서 결과를 출력하도록 한다.
만약 종료조건을 만족하지 않는다면 계속해서 프로그램이 진행되며 n+1, n-1, 2n의 값을 queue에 추가해주며 반복한다.
제출 코드
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
MAXRANGE = 100001 # N, K의 최대 범위가 100000이다
visited = [False for _ in range(MAXRANGE)] # 중복으로 q에 값이 들어감을 방지하기 위한 visited 배열이다.
def bfs(cur):
q = deque([])
c = 0 # 시간 초기값
q.append((cur,c)) # q에 초기값을 넣어준다.
while q:
n, cnt = q.popleft()
visited[n] = True # 방문 표시
if n==K: # K에 도달한 값을 출력
print(cnt)
break
for next_n in (n+1, n-1, 2*n): # n+1, n-1, 2*n을 모두 시행해보고 조건에 부합하면 q에 더해준다.
if 0 <= next_n < MAXRANGE and visited[next_n]==False: # 방문한적이 없는지, 범위내에 존재하는지 확인한다.
q.append((next_n,cnt+1))
bfs(N)