[BFS] 가중치가 동일한 그래프에서의 BFS / 4가지 연산을 이용하여 1 만들기

문제링크

https://www.codetree.ai/missions/2/problems/make-one-using-four-operations?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 특정한 '연산'을 이용하여 특정한 수 만들기 유형 - DP or BFS 유형의 문제
• BFS로 문제 풀이를 할 경우..
  • 기존에 방문했는지를 확인하는 in_queue와 도달거리를 확인하는 visited를 만들어야 하는데 이 문제의 유형은 2차원 그래프처럼 in_queue, visited의 크기가 딱 정해져 있지 않다. 따라서 dictionary를 이용해 판단하도록 한다.
  • 특정 연산 값을 너비 우선 탐색으로 확인할 것이므로 미리 num_list를 계산해둔다.
• 이 문제의 핵심은 연산 중에 '-1'이 존재하는 것이다. 숫자가 무조건 커지기만 하면 사실 기존의 값에 다시 도착하기 쉽지 않는데 -1 연산이 존재해 문제가 발생한다. 
  • 예를 들어, 11이 입력되었을 때 '-1연산'에 의해서 10으로 바뀐다. 그 후에 '+1연산'에 의해서 11로 다시 변경된다. 이 과정이 계속 반복되면 메모리초과가 나서 터지는 것이다.
  • 따라서 기존에 존재하는 값이 나오는 경우, 즉 우리가 기존 BFS문제 풀 때 in_queue가 False인 것을 확인하는 과정필요하다. 여기서 in_queue를 딕셔너리 자료구조를 사용했기 때문에 num_list에 존재하는 숫자가 in_queue에 있는지 확인한다.
  • 딕셔너리 구조이기 때문에 'in'으로 확인해도 시간 복잡도의 큰 문제는 발생하지 않는다.
• num_list에 '1'이 존재하면 더 이상 연산은 진행할 필요 없다. 
• 주의주의!!!
  • 연산 관련 BFS 문제에서 '곱하기'가 존재하면 num_list에 들어가는 숫자가 매우 커지게 된다. 예를 들어 곱하기 2를 하는 연산과 +1이 있는 연산이 있다고 생각해보자. 
  • 300에서 400을 가는데 bfs는 +1로 100번 이상 돌아야하는데 그만큼 곱하기 연산도 진행되면서 숫자가 매우매우 커지게 된다.
  • 따라서 이럴 때는, 큰 숫자에서 작은 숫자로 가는 '거꾸로 생각하기'를 하든가 범위를 제한해야한다.
• 유사한 문제

https://www.acmicpc.net/problem/16953

16953번: A → B

https://www.acmicpc.net/problem/25418 ★

25418번: 정수 a를 k로 만들기

728x90

2. 코드(Python)

# "최소" 연산 횟수 > 생각의 순서: dp - bfs/dfs - 그리디 순...

from collections import deque

n = int(input())
in_queue = {}
dist = {}

def bfs(n):
    dq = deque([])

    dq.append(n)
    dist[n] = 0
    in_queue[n] = True

    if n == 1:
        return 0

    while dq:
        cur = dq.popleft()

        num_list = [cur + 1,cur - 1]
        if cur % 2 == 0:
            num_list.append(cur // 2)
        if cur % 3 == 0:
            num_list.append(cur // 3)

        if 1 not in num_list:
            for nxt in num_list:
                # -1이 존재해서 기존에 갔던 것으로 되돌아 갈 수 있음.
                # 그렇게 11 > 10 > 11 > 10 > 11...무한
                # in_queue에 없다는 것을 확인한 후에 bfs 돌기 가능!
                if nxt not in in_queue:
                    dq.append(nxt)
                    in_queue[nxt] = True
                    dist[nxt] = dist[cur] + 1
        else:
            dist[1] = dist[cur] + 1
            break
    
    return dist[1]

print(bfs(n))