BOJ - 1107 리모컨

1107번 리모컨

티비 채널을 돌리려고 하는데 몇몇 버튼이 고장난 상황에서 원하는 채널 까지 버튼 누르는 최소 횟수를 구하는 문제이다.

현재 채널은 100번이며 +,- 버튼은 고장나지 않는다고 가정한다.

버튼 동작을 아래처럼 구분할 수 있다.

1. '+' : 현재 채널 +1
2. '-' : 현재 채널 -1
3. 숫자(한자리) : 해당 채널
4. 숫자(한자리 이상) : 숫자 누적

문제 해결을 위해 queue 자료구조를 선택하였다.

queue에 버튼 누른 후의 채널 번호, 누른 횟수, '+,-'를 눌렀을 때와 숫자를 눌렀을 때를 구별하기 위한 flag를 저장해 주었다.

'+,-'의 경우 채널 번호가 +1, -1이 되므로 비교적 간단하다.

숫자일 경우 만약 처음으로 숫자가 눌리는 상황이면 그냥 숫자를 저장하였고, 이미 숫자가 눌린 상태에서 숫자가 눌리는 상황이면 이전숫자x10 + 누른 숫자 를 저장해 주었다.

bfs를 활용하여 위의 경우들을 queue에 저장하며 원하는 번호가 나올 때 까지 반복하면 된다.

채널은 무한대 까지로 가정 되어있지만 원하는 채녈은 최대 500,000이므로 넉넉하게 범위를 1,000,011 로 해 주었다.

코드

#include <iostream>
#include <queue>

using namespace std;

int number[10];
int visited[1000011][2];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,m;
    cin >> n >> m;

    for(int i=0;i<m;i++)
    {
        int a;
        cin >> a;
        number[a] = 1;
    }

    queue<pair<pair<int,int>,int>> q;
    q.push(make_pair(make_pair(100,0),0));

    int num,cnt,flag;
    while(!q.empty())
    {
        num = q.front().first.first;
        cnt = q.front().first.second;
        flag = q.front().second;
        q.pop();

        if(num == n)
            break;

        if(visited[num][flag] == 1) {
            continue;
        }

        visited[num][flag] = 1;

        // +,- 일 때
        if(num < 1000011)
            q.push(make_pair(make_pair(num + 1, cnt + 1),0));
        if (num > 0)
            q.push(make_pair(make_pair(num - 1, cnt + 1),0));

        // 일반 번호 일 때
        if(flag == 1 || num == 100) {
            for (int i = 0; i < 10; i++) {
                if (number[i] == 1)
                    continue;

                if (flag == 1 && num * 10 + i < 1000011)
                    q.push(make_pair(make_pair(num * 10 + i, cnt + 1),1));
                else if(flag == 0)
                    q.push(make_pair(make_pair(i, cnt + 1),1));
            }
        }
    }

    cout << cnt;

    return 0;
}

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