[BaekJoon/백준] 5014번 스타트링크

 

코테 망하더니 정신줄을 놓은 것 같다.

 

기본적인 BFS 문제인데, 실수로 부분부분 코드를 하나씩 빼고 불완전하게 작성해서 자꾸 오류가 떴다.

#include <iostream>
#include <queue>


using namespace std;


int MAX, START, GOAL, U, D;

bool VISIT[1000001];
int DEPTH[1000001];

void bfs(int start) {
    
    queue<int> que;
    que.push(start);
    VISIT[start] = true;
    
    
    while(!que.empty()) {
        
        
        int x = que.front();
        
        que.pop();
        
        
        if(x + U <= MAX && !VISIT[x + U]) {
            que.push(x + U);
            
            DEPTH[x + U] = DEPTH[x] + 1;
            VISIT[x + U] = true;
            
            if(x + U == GOAL) // 굳이 더 이상 진행할 필요 없음
                return;
        }
        
        
        if(x - D >= 1 && !VISIT[x - D]) {
            que.push(x - D);
            
            DEPTH[x - D] = DEPTH[x] + 1;
            VISIT[x - D] = true;
            
            if(x - D == GOAL) // 굳이 더 이상 진행할 필요 없음
                return;

        }
        
    }
    
}

int main() {
    
    cin >> MAX >> START >> GOAL >> U >> D;
    
    bfs(START);
    
    if(VISIT[GOAL])
        cout << DEPTH[GOAL] << "\n";
    else
        cout << "use the stairs\n";
}

 

소요 시간 : 25분

 

 

유사한 문제

- 1697번 : https://hevton.tistory.com/422

- 2644번 : https://hevton.tistory.com/593