[백준] 16953번 : A → B (파이썬)

BFS 문제

 

 

(1) 처음에 내가 생각한 방식

 

#BFS
from collections import deque
import math
a,b=map(int,input().split())
queue = deque()
count=[]
ans=0

queue.append(a)
index=0
while queue:
    index+=1
    q = queue.popleft()
    if q==b:
        ans=math.ceil(math.sqrt(index))
        break
    queue.append(q*2)
    queue.append(int(str(q)+str("1")))

print(ans)

 

처음에 이 문제를 보자마자 나는 위와 같은 방식으로 풀었다. 하지만, 예제 입력 1이나 예제 입력 3처럼 공백을 기준으로 입력 받은 왼쪽 값에서 오른쪽 값으로 갈 수 있는 경우만 고려한 방식이었다. 즉, 예제 입력 2처럼 공백을 기준으로 입력 받은 왼쪽 값에서 오른쪽 값으로 갈 수 없는 경우는 고려하지 않은 코드였다. 위와 같은 코드는 예제 입력 2와 같은 입력이 들어왔을 경우, break문을 만나지 못하므로 무한 루프에 걸리는 코드이다. 처음에 직관적으로 짠 코드라서 이와 같은 예제는 고려하지 못하였었다.

 

ex) 2 162

# 2 → 4 → 8 → 81 → 162

 

2 

4 21 [2] 1

21 8 41 [4] 2

8 41 42 211 [21] 3

41 42 211 16 81 [8] 4

42 211 16 81 82 411 [41] 5

211 16 81 82 411 84 421 [42] 6

16 81 82 411 84 421 422 2111 [211] 7

81 82 411 84 421 422 2111 32 161 [16] 8

411 84 421 422 2111 32 161 162 811 [81]

 

-> (1)과 같은 방식으로 풀었을 때에 queue에 저장되는 값을 나열한 것이다. []안의 값은 queue에서 pop한 값이고, 파란색 글씨 부분이 index 변수 값을 의미한다. 우리는 queue에서 값을 하나 꺼내고, 값을 두개 넣어줄 때마다 index를 1씩 증가시킨다. 여기선, index의 제곱근을 올림한 값을 출력값으로 지정했는데, 문제가 있다.

다음 예를 들어 설명해보겠다.

input : 2 8 ---> index 값은 4이므로 제곱근은 2이다. 2->4->8 (실제값 : 2) O

input : 2 81 ---> index 값은 9이므로 제곱근은 3이다. 2->4->8->81 (실제값 : 3) O

input: 2 42 ---> index값은 6이므로 제곱근을 올림한 값은 3이다. 2->21->42 (실제값 : 2) X

 

이렇게 만족하지 않는 예시도 존재한다. 따라서, 이 문제에서 위와 같이 index를 따로 도입하고, 제곱근을 사용하는 것은 올바르지 못한 선택이었다.

 

(2) 코드 수정 후 내 코드 (성공)

 

#BFS
from collections import deque
import math
a,b=map(int,input().split())
queue = deque()
ans=-1

queue.append((a,1))
index=0
while queue:
    q,cnt = queue.popleft()
    if q==b:
        ans=cnt
        break
    if q>b:
        continue
    queue.append((q*2,cnt+1))
    queue.append((int(str(q)+str("1")),cnt+1))

print(ans)

 

일단, (1)에서의 방식처럼 불필요하게 index란 변수를 도입할 필요가 없기 때문에 이 부분을 수정해주었다. index 변수를 사용하여 출력값을 위한 준비를 따로 해주다 보면 어디선가 예기치 못한 변수가 발생할 수도 있다. 따라서, 처음에 queue에 append 해줄 때 set 형식으로 값을 추가해주었다. 또, 공백을 기준으로 오른쪽으로 입력 받은 값보다 queue에서 꺼낸 값이 더 크다면 continue를 사용하여, queue에 append하는 부분을 제외시켜주었다. 이로서, 무한루프 또한 벗어날 수 있게 되었다.