[백준(BOJ)] 5014번 : 스타트링크 - C++[CPP]

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

5014번: 스타트링크

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

BFS 문제라 BFS로 풀었는데 식으로도 충분히 풀 수 있다.

 

현재 층에 대해 위층과 아래층 값을 더하거나 뺀 값이 최고층보다 작거나 같거나, 0보다 크고 방문한 적 없는 층이라면 진행한다. 그리고 그 층을 다시 현재층에 대입하여 반복한다.

 

그러다가 목적층인 G와 현재층 S 값이 같다면 종료하고 값을 출력한다.

같지 않는다면 "use the stairs"을 출력한다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 1000001

int F, S, G, U, D;
int dx[2];
int visit[MAX]={0,};
bool flag=true;

void bfs() {
    queue<int> q;
    q.push(S);
    visit[S]=1;

    while(!q.empty()) {
        S = q.front();
        q.pop();

        for(int i=0;i<2;i++) {
            int nx = S + dx[i];
            
            if(nx>0 && nx<=F) {
                if(visit[nx]==0) {
                    visit[nx]=visit[S]+1;
                    q.push(nx);
                }
            }
            if(S==G) {
                flag=false;
                break;
            }
        }
    }
}

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

    dx[0]=U;
    dx[1]=-D;
    
    bfs();

    if(flag) cout << "use the stairs";
    else cout << visit[G]-1;
}

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!