[DFS/BFS/완전탐색] ▲ 16953번 - A → B(BFS)

[백준] 16953번 - A → B

풀이 시간: 40분이내

 

1) 문제 해결 아이디어

리플릿에서 코드를 짜고 실행을 했을 때는 graph크기를 (10**9 _+ 1) 로 생성하니 그냥 종료 되었다. 크기를 수정하니 전혀 문제가 없었으나 제출할 때 메모리 초과 오류가 생겼다.

코드를 짜는 것은 쉬웠는데 오류를 고치는데 시간이 많이 걸렸다.

모든 BFS 문제는 graph를 만들어서 문제를 푼다는 고정관념때문에 틀린 문제였다. 항상 graph를 만들어 문제를 풀다보니 자연스레 또 그래프를 만들 생각만 했던 것 같다.

BFS를 풀기 위해서는 큐만 있으면 된다!!

 

<동작과정>

1. 큐 생성 및 (시작값, 누적 연산횟수) 형태로 삽입

2. 2가지 연산 수행

2-1. 큐에서 하나 꺼내기

2-2. 2가지 연산한 결과값(nx)이 1보다 크고 b보다 작거나 같으면 큐에 삽입 (연산 결과값, 누적연산횟수 + 1)

(여기서 주의할 점은 누적 연산 횟수에 1을 더해서 넘겨주어야 한다는 것이다. nx가 연산을 1번 더 수행한 결과값이기 때문이다.)

3. 큐에 값이 없거나 꺼낸 값이 목표값(b)와 같을 때까지 2 반복

 

첫번째 오류. 메모리 초과

1. graph 크기와 2가지 연산을 한 값(nx)의 범위 변경 -> 또 실패

A, B의 범위는 (1 <= A < B <= 10**9) 이다.

그래서 처음에 graph를 (10**9 + 1) 의 크기로 생성하고 연산을 한 값이 위와 같은 범위내이면 큐에 담고 방문 처리를 하도록 했다.

하지만 2가지 연산 모두 시작 값보다 항상 큰 값을 반환하므로 B보다 커지게 되면 값을 굳이 큐에 넣을 필요가 없다!! 또한 graph도 항상 (10**9 + 1) 크기로 생성하지 않고 (b + 1)의 크기로 생성하였다. 하지만 이것으로도 여전히 문제가 해결되지 않았다.

 

2. graph를 없애고 큐에 (값, 연산횟수) 형태로 넣기 -> 성공!!

 

[참고] https://alpyrithm.tistory.com/118

[알고리즘][Python] 백준(BOJ) 16953 A → B_파이썬

 

2) 소스코드

from collections import deque

# BFS(현재값, 연산횟수)
def bfs(x, c):
  queue = deque()
  queue.append((x, c))

  while queue:
    x, c = queue.popleft()
    # B에 도달하면 종료
    if(x == b): 
      return c + 1
    # 2를 곱한 값, # 오른쪽에 1을 추가한 값
    dx = [2 * x, int(str(x) + "1")]
    
    for nx in dx:
      # 1보다 크고 목표값보다 작거나 같으면
      if(1 < nx <= b):
        # 삽입, 방문 처리
        queue.append((nx, c + 1))
  return -1     

a, b = map(int, input().split())  # 시작값, 목표값
print(bfs(a, 0))