탈출

탈출

문제

홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.

홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.

버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다.

버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.

1. 버튼 A를 누르면 N이 1 증가한다.
2. 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 예를 들어 123→146으로, 5→0으로, 3→5로 변한다. 단, N이 0이면 버튼 B를 눌러도 수가 변하지 않는다.
3. LED가 다섯 자리까지밖에 없기 때문에 N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
4. 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.

또한 홍익이는 최대 T회 버튼을 누를 수 있고, 그 횟수 안에 LED로 표현된 N을 G와 같게 만들어야 탈출할 수 있다는 사실을 알아냈다.

똑똑한 홍익이는 이와중에 자존심이 발동해 버튼 누르는 횟수를 최소로 하여 방을 탈출하기로 했다.

홍익이의 방 탈출을 기원하며, 탈출에 필요한 최소의 버튼 횟수를 구하자.

입력

첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다.

각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다.

출력

첫 번째 줄에 탈출에 필요한 최소의 버튼 횟수를 출력한다.

만약 탈출할 수 없다면 “ANG”을 따옴표 없이 출력한다.

예제 입력 1

1 7 10

예제 출력 1

7

버튼을 A A A B A A A 순서로 누르면

1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> 10 순서로 숫자가 변한다.

예제 입력 2

7142 10 7569

예제 출력 2

3

예제 입력 3

7142 1 7569

예제 출력 3

ANG

예제 입력 4

63429 99999 231

예제 출력 4

ANG

문제 해석

옛날에 DSLR이라는 문제를 풀어봤었다. D인 경우 어떠한 연산을 하고 S, L, R에 따라 각기 다른 연산을 하면서 정답을 찾아내는 최소의 알파벳을 찾아내는 건데 이 문제도 비슷하다. A, B에 따른 각 다른 연산이 존재하고, 어떠한 답에 도달했을 때 최소 경로를 찾는 것이다. bfs를 이용하여 queue에 이런 각기 다른 경우들을 append 해주면서 답을 찾아내는 것인데, 유의해야 할 것은 visited 리스트를 이용하여 특정 수를 방문을 한다면 그 수는 다시 queue에 넣지 않게끔 방문 처리를 해줘야 한다. 안 그러면 같은 수들이 계속해서 들어가면서 같은 연산이 2 ^ n 번 만큼 반복이 되기 때문이다.

풀이

• 만약 N == G (입력 받은 수와 도달해야 하는 수가 같은 경우)
  • 1번도 연산 안해도 도달해야 하는 수와 같기 때문에 0을 출력해주고 시스템을 종료한다.
• bfs 함수 선언
  • flag = 0 (while문을 다 돌았는데 수에 도달하지 못하는 경우를 위해)
    - 만약 count == T (최대 계산 가능 횟수)
    - continue (가장 먼저 최대 도달 횟수에 그 다음에 정답이 나올 수도 있기 때문에 break가 아닌 continue를 해준다.)
    - A인 경우
    - N_A = N + 1 해줌
    - 만약 N_A == G (G라는 수에 도달한다면 break를 하는데 최소 비용이기 때문에 가장 먼저 계산이 된 결과가 최소 비용이다.)
    - print(count + 1)
    • flag = 1 (while문 다 돌기 전에 수를 찾아서 ANG을 출력 안하기 위해 flag를 1로 바꿔준다.)
      - break
      • 만약 N_A != 99999 (99999가 되면 그 다음 연산 결과들은 무조건 넘어가기 때문에 queue에 appen 해줄 필요가 없음)
        - queue에 append (N_A, count + 1)
      • 만약 N != 0
    • N_B = N * 2
      • 만약 N_B > 99999
        • continue
      • 그게 아니라면?
        • list_N_B = list(N_B)
        • list_N_B[0] -= 1
        • 루프
          • a += list_N_B[i] * (10 ** (len(list_N_B) - 1 - i))
          • 자릿수를 이용해서 10의 제곱만큼 각 자리에 맞게 곱해주면서 a에 더해준다.
        • 만약 a == G
          • print(count + 1)
          • flag = 1
          • break
        • queue에 append (a, count + 1)
      • 만약 flag == 0:
    • while문을 다 돌았는데도 수를 못 찾은 것이기 때문에 ANG을 출력해준다.

import sys
from collections import deque

N, T, G = map(int, sys.stdin.readline().split())

queue = deque()
queue.append((N, 0))
visit = [0] * 100000

if N == G:
    print("0")
    exit()

def bfs():
    N_A = 0
    N_B = 0
    while queue:
        flag = 0
        N, count = queue.popleft()
        if count == T:
            continue
        N_A = N + 1
        if N_A == G:
            print(count + 1)
            flag = 1
            break
        if N_A < 100000 and visit[N_A] == 0:
            visit[N_A] = 1
            queue.append((N_A, count + 1))
        if N != 0:
            N_B = N * 2
            if N_B > 99999:
                continue
            else:
                list_N_B = list(str(N_B))
                c = int(list_N_B[0])
                c -= 1
                list_N_B[0] = str(c)
                a = 0
                for i in range(len(list_N_B)):
                    a += int(list_N_B[i]) * (10 ** (len(list_N_B) - 1 - i))
                # a = str(N_B)
                # a = str(int(a[0]) - 1) + a[1:]
                if int(a) == G:
                    print(count + 1)
                    flag = 1
                    break
                if visit[int(a)] == 0:
                    queue.append((int(a), count + 1))
                    visit[int(a)] = 1
    if flag == 0:
        print("ANG")
                           
bfs()        

고찰

• 코드를 다 짜고 나서 계속 21퍼센트에서 틀리기에 계속 고민을 했다.
• 한가지 예외 처리를 안해준 것이, 입력 받은 수와 도달 해야 하는 수가 같은 경우이다.
• 이 경우는 한번의 연산도 없이 도달해야 하는 수에 도달했기 때문에 0을 출력을 해줘야한다.
• 그리고 맨 앞자리에서 1을 빼주는 경우인데
• 필자는 리스트를 이용하여 0번지의 수를 1빼주고 자릿수 만큼 10의 n승을 곱해줘서 숫자를 만들었는데
• 파이썬의 slicing 을 이용하면 주석처리한 코드처럼 쉽게 해결할 수 있다.