1107_리모컨

브루트포스 문제인데, 재귀로 풀어야할지 아니면 최소를 구하는 문제니까 BFS로 풀어야할지 감이 안왔다.

그리고 탐색을 하려면 각 노드의 이웃을 알아야하는데, 그동안은 이웃 노드가 상/하/좌/우 처럼 정해져 있는 문제만 풀어본 것 같아서, 숫자 버튼도 누를 수 있고 +, - 버튼도 누를 수 있는 이 문제에서는 이웃 노드를 어떻게 저장해야 할지 모르겠었다.

결론은 두가지 방법 다 아닌 새로운 로직으로 풀어야 했다.

모든 채널에 대해 완전 탐색을 진행했다. 눌러야 하는 (숫자 버튼 개수) + (+/- 버튼 개수) 를 구하면서 최솟값을 갱신했다.

#include <iostream>
#include <cmath>

using namespace std;

int n, m;
bool broken[10];

int number_button(int channel) { // 해당 채널로 이동하기 위해서 눌러야 하는 '숫자 버튼'의 개수 반환
    if (channel == 0) { // 이동하려는 채널이 0 인 경우 예외 처리
        if (broken[channel]) return 0;
        else return 1;
    }

    int cnt = 0;
    while (channel > 0) {
        if (broken[channel % 10]) return 0; // 고장난 버튼인 경우
        channel /= 10;
        cnt++;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        broken[x] = true;
    }

    int ans = abs(n - 100); // +/- 버튼으로만 이동하는 횟수로 초기화
    for (int i = 0; i < 1000000; i++) {
        int numberCnt = number_button(i); // 눌러야 하는 '숫자 버튼'의 개수
        if (numberCnt > 0) {
            int plusMinusCnt = abs(i - n); // 눌러야 하는 '+/- 버튼'의 개수
            int tmp = numberCnt + plusMinusCnt; // 총 개수
            if (ans > tmp) {
                ans = tmp;
            }
        }
    }
    cout << ans << '\n';

    return 0;
}