[BAEKJOON] 1107 리모컨

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

1107번: 리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.

---

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다.
고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

---

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

---

풀이

처음에는 그리디 알고리즘으로 접근했었는데 몇가지 경우에서 예외가 발생했다.

결국에 모든 경우의 수를 확인하는 브루트포스 알고리즘으로 접근. 

 

로직

1. 필요한 입력을 받고 정상 버튼을 구하기
2. 현재 위치에서 최소 카운트 구하기
3. queue에 초기값 넣고 모든 경우의 수 탐색
4. 고장난 버튼이 없다면 입력받지 말기

 

제출 코드

from collections import deque
from sys import stdin
input = stdin.readline

n = int(input())
m = int(input())
normal_bnt = set(num for num in range(10)) - (set(map(int, input().split())) if m else set())

min_cnt = abs(100 - n)
queue = deque([''])

if m < 10:
    while queue:
        num = queue.popleft()
        for btn in normal_bnt:
            temp_num = num + str(btn)
            min_cnt = min(min_cnt, abs(n - int(temp_num)) + len(temp_num))

            if temp_num != '0' and len(temp_num) < 6:
                queue.append(temp_num)

print(min_cnt)
# 37636KB, 992ms, 560B

결과만 보면 어렵지 않은 문제지만 푸는데 좀 오래걸렸다.

모든 경우의 수를 탐색하면서 수를 만드는 과정과 조건문으로 queue에 넣는 조건이 은근 까다로웠다.

마지막으로 고장난 버튼이 없을 때와 모두 고장났을 때를 고려해서 추가로 조건을 깔끔하게 구성하는것이 어려웠다.

 

로직에 문제가 없는 것 같지만 답이 틀리다고 나온다면 위 경우를 생각해보는것이 좋을 듯 하다.