[백준/Baekjoon] 5014 스타트링크 C++ :: BFS

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

5014번: 스타트링크

---

1. Logic

기본 BFS 문제이다.

 

최소 이동을 고르기 때문에 우선순위 큐를 활용해서 버튼을 누르는 횟수가 가장 작은것들을 먼저 빼줬고, if문으로 조건을 나눌 때 계속 OutOfBounds가 나와서 잠깐 막혔는데, if문에서 거를 때 조건 두개가 and연산으로 묶여있으면 앞에 조건을 먼저 탐색하기 때문에if문 조건 순서를 바꿔서 해결해줬다

if(cur-d >= 1 && !vis[cur-d]) 이 부분에서 원래는 if( !vis[cur-d] && cur-d >= 1) 이렇게 썼는데 이러면 vis[cur-d]값을 참조하기 때문에 OutOfBounds가 떴다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int f, s, g, u, d;

bool vis[1000001];


int bfs() {
    priority_queue<pair<int, int>> q;
    
    q.push({0, s});
    vis[s] = true;
    
    while(!q.empty()) {
        int cur = q.top().second;
        int cnt = -q.top().first;
        
        q.pop();
        
        if(cur == g) {
            return cnt;
        }
        
        if(cur-d >= 1 && !vis[cur-d]) {
            vis[cur-d] = true;
            q.push({-(cnt+1), cur-d});
        }
        
        if(cur+u <= f && !vis[cur+u]) {
            vis[cur+u] = true;
            q.push({-(cnt+1), cur+u});
        }
    }
    cout << "use the stairs";
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> f >> s >> g >> u >> d;
    
    cout << bfs();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90