[C++] 백준 5014번: 스타트링크

문제

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

 

풀이

queue를 이용한 BFS로 풀어주었다.

 

❎ 오답 과정

 

66%에서 틀렸습니다. 를 11번이나 봤는데 범위 체크가 원인이었다. 

#define MAX 1000000

bool isVaild(long long a)
{
    if( a > MAX || a > F || a <= 0)
        return false;
    return true;
}

 

1. 100,000층 (MAX)범위를 초과 하는지
2. 최고 층(F)를 초과하는지
3. 0층으로 이하로 가는지

3가지를 꼭 조건으로 달아주어야 한다.

 

백준 싹싹 뒤져서 반례 다 돌렸는데도 왜 틀렸는지 모르겠어서 힘들었는데

MAX 범위 추가 하나 추가해서 맞췄다. 범위 체크 잘 하자 😭

 

반례 모음

158 9 70 9 16
정답: 29
    
80 45 32 5 19
정답: 7
    
14 6 10 2 3
정답: 2
    
15 1 7 2 1
정답: 3

16 4 10 3 2
정답: 2

5 1 1 2 2
정답 : 0

2 2 1 0 1
정답: 1

 

소스

#include <iostream>
#include <queue>
#define MAX 1000000
 
long long F, S, G, U, D;
 
bool isVaild(long long a)
{
    if( a > MAX || a > F || a <= 0)
        return false;
    return true;
}
 
int main()
{
    bool visited[MAX+1];
    int answer = 0;
    bool flag = false;
    
    std::cin >> F >> S >> G >> U >> D;
    
    std::queue<long long> q;
    q.push(S);
    visited[S] = true;
    
    if(S == G)
    {
        std::cout << 0;
        exit(0);
    }
 
    while(!q.empty())
    {
        if(flag) break;
        
        long long qSize = q.size();
        while(qSize--)
        {
            long long now = q.front(); q.pop();
            if(now == G)
            {
                flag = true;
                break;
            }
            
            long long up = now + U;
            long long down = now - D;
            
            if(isVaild(up) && !visited[up])
            {
                visited[up] = true;
                q.push(up);
            }
            
            if(isVaild(down) && !visited[down])
            {
                visited[down] = true;
                q.push(down);
            }
        }
        ++answer;
    }
    
    if(visited[G])
        std::cout << answer - 1;
    else
        std::cout << "use the stairs";
    
    return 0;
}