Concept

• N 채널에 도달하는 방법에는 두 가지가 있다.
  1. +/- 버튼만 누르는 경우:
     100 채널에서 N 채널까지 +/- 버튼만 눌러서 가는 방법
  2. 숫자 버튼을 누르는 경우:
     숫자 버튼들을 눌러 특정 x 채널에 가고, 필요한 경우 +/- 버튼도 추가로 몇 번 누르는 경우
• 이 두 가지를 비교해서, 버튼 누르는 최솟값을 구해야 한다.
  • 첫 번째 경우는 abs(N - 100).
    • 숫자 버튼이 고장나는 것봐 별개로 항상 실행 가능한 케이스이기 때문에 이 값을 min_cnt의 최초값으로 설정했다.
  • 두 번째 경우는 ((x채널에 도달하기 위해 숫자 버튼 누른 횟수) + abs(x - N))).
    • x 채널을 구하기 위해 bfs를 이용했다.
    • bfs로 여러 x 채널을 탐색하면서 min_cnt 값을 업데이트해준다
• bfs 탐색 이후 min_cnt를 출력하면 된다
  

BFS 원리

• 매 노드마다 버튼 눌러야 하는 횟수를 구하고,
• 그 횟수를 min_cnt과 비교하여 min_cnt를 업데이트한다.
• 이후 다음 탐색할 노드를 구해 queue에 추가해준다.
• 다음 노드는 현재 노드(x 채널)에다가 다음 누를 숫자 버튼을 추가한 것이다.
  • 가령, '123'이 현재 노드이면, 다음 노드는 고장나지 않은 숫자 버튼들을 각각 하나씩 더한 채널이다.
  • 고장나지 않은 숫자 버튼이 [1, 2, 3, 4, 5] 이면 다음 노드들로는 '1231', '1232', '1233', '1234', '1235'이다.
• 이 bfs는 x 채널값이 N보다 클 경우 탐색을 그만한다.
  • 이유
    • x 채널값이 계속 크면, +/- 버튼을 더더욱 많이 눌러야 하기 때문에 버튼 누르는 횟수는 계속 커질 것이다.
    • 즉, x 채널값이 N보다 많이 크면 버튼 누르는 횟수가 최솟값일 수가 없기 떄문이다.
      한편 x <= N이면, x 채널값이 계속 크면 오히려 x가 N과 더욱 가까워지기 때문에 새로운 최솟값을 구할 수 있기에,
      이 경우엔 탐색을 계속 한다.
  • 단 N보다 크더라도, N과 x 채널 값의 차이가 크지 않으면 최솟값일 수 있다.
  • 그렇기에 x 채널값이 N보다 큰 경우, 버튼 누르는 횟수를 구해 min_cnt를 업데이트하되, 다음 노드를 구하지 않는다. 즉, 더이상 숫자 버튼을 누르지 않는다.

Point

• 고장난 버튼이 없는 경우 (M = 0):
  • 이 경우는 1번 경우와 숫자 버튼만 누른 경우밖에 없기 때문에, 그 둘을 비교하여 최솟값을 출력해주면 된다.
• 0번 버튼을 누르는 경우:
  • bfs에서 0번을 여러번 눌러도 x 채널값은 계속 0이다.
  • 그럴 경우 x > N일 수가 없기에 무한 탐색이 이어지며, 그렇기에 0 버튼을 계속 누르는 것을 막는 조건이 필요하다.
  • 이를 위해, 처음에 한번만 0 버튼을 누른 경우만 버튼 누르는 횟수를 구하고, 이후 또 0번 채널이면 탐색을 멈추는 조건을 넣어줬다.
  • queue 초기값에는 0이 들어가있고, 탐색을 이어나가는 조건으로 0 < x <= N 조건문을 넣으면 된다.

코드

import sys
from collections import deque

input = sys.stdin.readline

if __name__ == '__main__':
     N = int(input())
     M = int(input())
     min_cnt = abs(N - 100)   # +/- 버튼만 누른 경우
     
     if M:
          btn = set(map(str, set(range(10)).difference(set(map(int, input().split())))))  # 고장나지 않은 버튼들
          q = deque([i for i in list(map(str, btn))])
     
          while q:
               num = int(q.popleft())
               num_str = str(num)
               min_cnt = min(min_cnt, abs(num - N) + len(num_str))
               if 0 < num <= N:
                    for next in btn:
                         q.append(num_str + next)
     else:
          min_cnt = min(min_cnt, len(str(N)))
     print(min_cnt)