[Algorithm] Baekjoon 1107번 : 리모컨

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

1107번: 리모컨

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
 
using namespace std;
 
 
vector<int> cNum;
int minCount = 10000000;
 
 
struct Node
{
    string s;
};
 
 
int BFS(int targetNum)
{
    int answer = 1000000000;
    queue<Node> q;
    q.push({""});
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        if (curNode.s.size() > 0)
        {
            int curNum = stoi(curNode.s);
            int temp = curNode.s.size() + abs(targetNum - curNum);
            answer = min(answer, temp);
 
            if (curNode.s.size() >= 6)
            {
                break;
            }
        }
        
        for (int i = 0; i < cNum.size(); i++)
        {
            string temp = curNode.s;
            temp += cNum[i] + '0';
 
            if (temp.size() > 6) continue;
            q.push({ temp });
        }
    }
 
    return answer;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    string target; // 목표채널
    int m = 0;
    int temp = 0;
 
    map<int, bool> icm;
 
    int start = 100;
 
    cin >> target >> m;
    
    if (m == 0) // 고장난 버튼이 없을경우
    {
        cout << min(abs(100 - stoi(target)), (int)target.size());
        return 0;
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> temp;
        icm[temp] = true;
    }
 
    for (int i = 0; i <= 9; i++)
    {
        if (!icm[i])
            cNum.push_back(i);
    }
 
    cout << min(BFS(stoi(target)), abs(stoi(target) - start));
 
    return 0;
}
 
 
 

BFS로 해서 통과는 했는데, 성능이 매우 안좋다. 불필요한 노드가 너무 많이 만들어지는듯하다.

나중에 다시 DFS쪽으로 풀어봐야겠다.. 풀어야할 문제가 너무 많아서 조금 미뤄둔다.