백준 1697 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

문제를 풀기 전에 먼저 정답 비율이 눈에 들어왔다.

 

지레 겁을 먹고 문제를 읽었다.

 

못 풀었다.

 

처음에는 dp 문제인 줄 알았다.

 

하지만 아무리 생각해도 dp로 풀리지 않았다.

 

그래서 정답을 참고했다.

 

bfs란다.

 

코드

import sys

input=sys.stdin.readline

from collections import deque

n,k=map(int,input().split())

 

max_num=100000

visited=[0]*(max_num+1)

def bfs():

  q=deque()

 

  q.append(n)

 

  while q:

    x=q.popleft()

 

    if x==k:

      print(visited[x])

      break

 

    for i in (x-1,x+1,x*2):

      if 0<=i<=max_num and visited[i]==0:

        visited[i]=visited[x]+1

        q.append(i)

bfs()

 

아직 갈길이 멀어도 너무 멀다.

 

아참, 이제 드디어 시험이 끝났다.

 

7월이 오기전에 골드를 달아 봐야겠다.

 

배운 점

1. for i in (a, b, c)로 인자를 직접 정해 줄 수 있다.