[C++] 백준 16397번: 탈출

🔗문제

16397번: 탈출

16397번: 탈출

 

🖍풀이

 

문제의 조건들만 잘 유의하면 바로 풀 수 있다.

 

어떤 경로를 통해서 값이 나왔는지 알고 싶어서 구조체를 이용해 풀었다.

struct pair
{
public:
    std::string str;
    int num;

    pair(int _num, std::string _str)
    :num(_num), str(_str){};
};

• str: 경로
• num: 번호

 

BFS를 이용해 풀었기 때문에 G값에 처음 도달한게 최소 경로다.

문제에 T라는 조건이 있었기에 출력할 때 조건을 달아준다.

if(str.size() <= T)
	std::cout << str.size();
else
	std::cout << "ANG";

 

🅱️ B 버튼

B 버튼을 눌렀을 때 조건이 까다롭기 때문에 여길 잘 짜야 한다.

최고 자릿수를 구하는데에 시간을 제일 많이 썼다 ^^;

int B(const int input)
{
    int digit = 1;
    int tmp = input * 2;
    
    if(!isValid(tmp))
        return -1;
    else
    {
        while(tmp >= 10)
        {
            tmp/=10;
            digit*=10;
        }
    }
    return input*2 - digit;
}

1. N*2가 MAX값을 넘는다면 탈출 실패다.
2. N*2했을 때 최고 자리수를 구해 digit에 저장한다.

 

최고 자리수 구하기

while(tmp>=10) // 10 이상 숫자가 맨 앞 자리수 하나만 남으면 정지한다.
{
	tmp/=10; // 10 -> 1, 123 -> 12
	digit*=10; // 1->10, 10->100
}

 

💾 소스

#include <iostream>
#include <queue>
#include <string>
#define MAX 100000

bool isValid(const int num)
{
    if(num < 0|| num > MAX-1)
        return false;
    return true;
}

struct pair
{
public:
    std::string str;
    int num;
    pair(int _num, std::string _str)
    :num(_num), str(_str){};
};

int B(const int input)
{
    int digit = 1;
    int tmp = input * 2; // 최고 자리수 구하기
    
    if(!isValid(tmp))
        return -1;
    else
    {
        while(tmp >= 10)
        {
            tmp/=10;
            digit*=10;
        }
    }
    return input*2 - digit;
}

int main()
{
    std::queue<pair> q;
    std::string str = "";
    bool visited[MAX+1] = {false, };
    int temp, a, b;
    int N, T, G;
    
    std::cin >> N >> T >> G;

    q.push({N, ""});
    visited[N] = true;
    
    while(!q.empty())
    {
        temp = q.front().num;
        str = q.front().str;
        q.pop();
        
        if(temp == G)
        {
            if(str.size() <= T)
                std::cout << str.size();
            else
                std::cout << "ANG";
            return 0;
        }

        a = temp+1;
        if(!visited[a] && isValid(a))
        {
            q.push({a, str + 'A'});
            visited[a] = true;
        }

        b = B(temp);
        if(!visited[b] && isValid(b))
        {
            q.push({b, str+'B'});
            visited[b] = true;
        }
    }

    std::cout << "ANG";
    return 0;
}