백준 5014번 스타트링크 (C++)

문제 링크 : https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수를 선언하고 값을 입력 받는다. 이때 f + 1의 사이즈 만큼 bool문형 배열을 선언한다.

    int f,s,g,u,d;
    cin >> f >> s >> g >> u >> d;
    vector<bool> ch(f+1,false);

참고로 bool ch[1000001]로 선언해도 무방하다.

이럴경우 memset이나 별도의 방법을 활용해 배열의 값을 false로 초기화 하는것을 잊지말자.

참고로 char 배열의 최대크기만 해도 백만까지 이므로, bool문의 배열 사이즈를 100만으로 설정해도 stack over flow가 나지 않는다.

 

2. 현재 층수와 누적 버튼 누름 횟수를 저장할 큐를 생성한다. 그리고 최초의 층을 방문표시 해준다.

    queue<pair<int,int>> q;
    q.push({s,0});
    ch[s] = true;

 

3. 다음은 while문의 코드이다.

    while(!q.empty()){
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(now==g){
            cout << cnt << "\n"; // 1
            exit(0);
        }
        if(now+u<=f&&now+u>now&&!ch[now+u]) { ch[now+u] = true; q.push({now+u,cnt+1}); } // 2
        if(now-d>=1&&now-d<now&&!ch[now-d]) { ch[now-d] = true; q.push({now-d,cnt+1}); } // 3
    }   

(1) 현재 위치가 목표층수라면 누적 버튼 누름 횟수를 출력하고 종료한다.

(2) 이 코드는 위 층으로 올라가는 코드이다. 현재 위치 + u의 값이 f 이하이며, 동시에 현재 위치 + u의 값이 현재 위치보다 높고, 현재 위치 + u의 층을 방문한 적이 없다면 방문 표시를 해주고 큐에 삽입해준다. 붉게 밑줄친 부분은 u의 값이 0일 경우를 방지하기 위함이다.

(3) 이 코드는 아래 층으로 내려가는 코드이다. 현재 위치 - d의 값이 1이상이며, 동시에 현재 위치 - d의 값이 현재 위치보다 낮고, 현재 위치 - d의 층을 방문한 적이 없다면 방문 표시를 해주고 큐에 삽입해준다. 파랑색 문장은 건물이 1층부터 시작하기 때문이며, 붉은색 문장은 d의 값이 0인 경우를 방지하기 위함이다.

 

4. while문을 빠져나온다면 엘리베이터로 이동할 수 없는 층이라는 뜻 이므로, "use the stairs"를 출력한다.

 

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int f,s,g,u,d;
    cin >> f >> s >> g >> u >> d;
    vector<bool> ch(f+1,false);
    queue<pair<int,int>> q;
    q.push({s,0});
    ch[s] = true;
    while(!q.empty()){
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(now==g){
            cout << cnt << "\n";
            exit(0);
        }
        if(now+u<=f&&now+u>now&&!ch[now+u]) { ch[now+u] = true; q.push({now+u,cnt+1}); }
        if(now-d>=1&&now-d<now&&!ch[now-d]) { ch[now-d] = true; q.push({now-d,cnt+1}); }
    }    
    cout << "use the stairs" << "\n";
    return 0;
}

위 코드는 vector 활용한 동적할당이며, 아래 코드는 bool문형 배열 [1000001]을 선언한 코드의 결과이다.