[백준/파이썬] 1107번 리모컨

solved.ac Class 3레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/1107

1107번: 리모컨

문제 해석

고장난 리모컨 버튼이 주어진다.

누를 수 있는 버튼은 +, - 버튼과 고장나지 않은 숫자 버튼이다.

해당 리모컨을 주어진 채널에 최소로 도달하는 횟수를 구하는 문제이다.

문제 풀이

이동할 수 있는 채널은 500,000 이지만 숫자를 누르고, (+, -) 버튼을 통해 이동하는 경우의 채널은 1,000,000을 넘을 수 없다. 

1. 누를 수 있는 숫자만 구하기
2. 누를 수 있는 숫자를 bfs를 통해 만들어가기
3. (만들어진 수 - 목표한 수)의 절대값이 이동한 횟수 이므로 답을 갱신해준다.
4. 100번 채널에서 시작하므로 (100 - 목표한 수)의 절대값 또한 최소 횟수 인지 확인해주어야 한다.

문제 코드

from collections import deque

def push_number_bttn(k, cur_channel, bttns):
    # 숫자 버튼
    return int(cur_channel + str(bttns[k]))

def solve(target_channel, n, bttns):
    visit = [0] * 1_000_001
    q = deque()
    q.append("")
    answer = abs(target_channel - 100)

    count = 1
    while q:
        for _ in range(len(q)):
            cur_channel = q.popleft()
            for k in range(len(bttns)):
                next_channel = int(push_number_bttn(k, cur_channel, bttns))
                if not(0 <= next_channel < 1_000_001): continue
                if visit[next_channel] == 0:
                    visit[next_channel] = 1
                    q.append(str(next_channel))
                answer = min(answer, abs(next_channel - target_channel) + count)

        count += 1
    return answer

channel = int(input())
n = int(input())
bttns = []
if n:
    broken_bttns = list(map(int, input().split()))
    for i in range(10):
        if i in broken_bttns: continue
        bttns.append(i)
else:
    for i in range(10):
        bttns.append(i)
print(solve(channel, n, bttns))

제출 결과

시작 채널번호가 100이라서 1001, 1002, 1003 ... 형태로 숫자를 붙여서 풀어 계속 틀렸다..
리모컨의 숫자를 누르면 누른 숫자부터 붙여가는데..