[BOJ] 리모컨

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

두 가지 방법으로 풀었다.
첫번째는 다익스트라를 응용한 방식이고
두번째는 완전탐색으로 풀었다.

풀이 설명

풀이 설명에 앞서 숫자버튼을 입력해서 옮기는 채널 번호를 몇까지 고려해야 하는가

-> 100에서 시작해서 50000까지 간다고 가정 해보면 +버튼으로만 한 칸씩 가도 49900번이면 도착하므로 약 100000 이후로는 고려할 필요가 없음
결론을 도출하면 도착해야 하는 번호 n의 2배까지만 고려하면 되는데 이렇게 코드를 짜면 틀렸다고 나온다. 이유는 n이 100보다 작은 경우에 반례가 생길 수 있는데 반례는 스스로 한번 생각해 보길

1. 다익스트라 응용 방식
   1) dist 배열을 전부 INF로 초기화 해준다.
   2) 입력을 받으면서 broken 배열에 고장난 번호를 체크한다.
   3) i=0부터 1000000 까지 돌면서 고장난 버튼이 하나도 없는 경우에 자리수로 dist를 갱신하고 우선순위큐에 넣고 시작 위치인 100도 넣는다.
   4) 다익스트라를 돌면서 최단거리를 갱신한다.
   5) dist[n] 출력

2. 완전탐색 방식
   1) 입력을 받으면서 broken 배열에 고장난 번호를 체크한다.
   2) ans를 한칸씩 이동해서 도착하는 거리로 초기화 해준다.
   3) i=0부터 1000000 까지 돌면서 고장난 버튼이 하나도 없는 경우에 그 번호를 누르는 횟수와 그 번호부터 n까지의 거리를 더해서 ans보다 작은 경우에 ans를 갱신한다.
   4) ans 출력

코드

1. 다익스트라 응용

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int INF = 987654321;
const int N = 500000;
int dist[2 * N + 1];
bool determined[2 * N + 1];
bool broken[10];
priority_queue<pair<int, int>> pq;

//배열 초기화
void init() {
    for (int i = 0; i <= 2 * N; ++i)
        dist[i] = INF;
    memset(determined, 0, sizeof(determined));
    memset(broken, 0, sizeof(broken));
}

int main(void) {
    init();

    int n, m;
    scanf("%d %d", &n, &m);
    //고장난 버튼 체크
    for (int i = 0; i < m; ++i) {
        int btn;
        scanf("%d", &btn);
        broken[btn] = true;
    }

    // dist 배열 초기화
    //아래 while문에서 temp!=0 조건으로 돌기때문에 i==0일때는 따로 처리해준다
    if (!broken[0]) {
        dist[0] = 1;
        pq.push({-dist[0], 0});
    }
    for (int i = 1; i <= 2 * N; ++i) {
        //숫자에 고장난 버튼이 하나라도 있으면 continue
        int temp = i;
        bool flag = false;
        while (temp != 0) {
            if (broken[temp % 10]) {
                flag = true;
                break;
            }
            temp /= 10;
        }
        if (flag)
            continue;

        //숫자버튼으로 갈수있는 번호 거리 지정해주기
        dist[i] = (int)log10(i) + 1;
        pq.push({-dist[i], i});
    }

    //다익스트라
    //시작위치
    dist[100] = 0;
    pq.push({-dist[100], 100});

    while (!pq.empty() && !determined[n]) {
        int cur = pq.top().second;
        pq.pop();

        if (determined[cur])
            continue;
        determined[cur] = true;

        //+, - 버튼으로 갈수있는 번호, 거리가 더 짧으면 거리갱신하고 우선순위큐에 넣기
        for (int i = 0; i < 2; ++i) {
            int next = cur + 2 * i - 1;
            if (next < 0)
                continue;
            if (dist[next] > dist[cur] + 1) {
                dist[next] = dist[cur] + 1;
                pq.push({-dist[next], next});
            }
        }
    }
    //출력
    printf("%d", dist[n]);
    return 0;
}

2. 완전탐색

#include <iostream>
#include <cmath>
using namespace std;
bool broken[10];

// 고장난 버튼이 있는 번호인지 체크
bool notBroken(int num) {
    if (num == 0 && broken[0])
        return false;
    while (num != 0) {
        if (broken[num % 10])
            return false;
        num /= 10;
    }
    return true;
}
int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int btn;
        scanf("%d", &btn);
        broken[btn] = true;
    }
    // ans 초기화
    int ans = abs(n - 100);
    for (int i = 0; i <= 1000000; ++i) {
        if (!notBroken(i))
            continue;
        //숫자 버튼으로 갈 수 있으면 가고 n까지의 거리만큼 더해서 ans보다 작으면 갱신
        ans = min(ans, abs(n - i) + (i == 0 ? 0 : (int)log10(i)) + 1);
    }
    printf("%d", ans);
    return 0;
}