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

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 bfs 개념을 배우고 난 뒤 첫 문제였습니다 ㅎ. 입문용으로 최고의 문제인 듯합니다. 

---

2. 풀이 과정

• 문제 해결의 흐름 
  1. 강호의 위치 S층에서 꼭대기 층인 F층 사이를 오르락(U) 내리락(D)하기.
  2. 이동하며 방문한 층은 방문처리한다. 이때, 이동한 층이 스타트링크가 위치한 곳(G)이라면 결과값을 제출하자.
• 나의 코드 

#include <iostream>
#include <queue>
using namespace std;

int F, S, G, U, D;
int visited[1000001] = {};
queue<int> q;

// bfs로 구현
int bfs() {
    visited[S] = 1;
    q.push(S);

    while (!q.empty()) {
        int now = q.front(); // 현재 층
        q.pop(); // front 삭제
        if (now == G) return visited[G]; // 도달했다면

        int go_up = now + U;    // 올라간다면
        int go_down = now - D;  // 내려간다면

        // 올라갈 수 있나?
        if (go_up <= F && !visited[go_up]) {
            visited[go_up] = visited[now] + 1;
            q.push(go_up);
        }

        // 내려갈 수 있나?
        if (go_down >= 1 && !visited[go_down]) {
            visited[go_down] = visited[now] + 1;
            q.push(go_down);
        }
    }

    // 엘리베이터로 이동할 수 없을 때
    return -1;
}

int main() {
    cin >> F >> S >> G >> U >> D;

    int result = bfs();

    if (result == -1) cout << "use the stairs";
    else cout << result - 1; // 버튼 누른 횟수를 반환해야하니 1을 빼줘야한다.


    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들 
  • ⭐️ 방문 처리 배열을 통해 눌러야 하는 버튼 수의 최솟값을 나타낼 수 있다.

---

3. 후기 

 전형적인 bfs 문제 ㅎ