[백준 5014번] python, c++ - 스타트링크

백준 5014 - 스타트링크

시간 제한 1초, 메모리 제한 256MB

# 조건

• 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다.
• 오늘은 강호의 면접날이다.
• 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.
• 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다.
• 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.
• 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다.
• U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)
• 강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.
  • 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

• 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000)
• 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

• 첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다.
• 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

# 접근 방법

• bfs를 활용하여 풀어주면 된다.
• 우선 현재 층이 목표 층보다 낮은데 D버튼의 값이 0이거나 높은데 U버튼의 값이 0인 경우 바로 use the stairs를 출력해준다.
• 그렇지 않은 경우 bfs() 함수를 실행해준다.
• 현재 층의 값을 q에 넣고 visited 배열에 1로 표시해준다.
• 이후, U버튼의 값을 더해준 val1, D버튼의 값을 빼준 val2 변수를 선언해주고, 범위 내이고 방문한 적 없다면 q에 담아준다.
• G 층에 도착한 경우 visited[G] -1을 return 해주고, 도착하지 못한 경우 use the stairs를 리턴해준다.

python 풀이

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import deque

def bfs():
    q = deque()
    q.append(S)
    visited = [0] * 1000001
    visited[S] = 1
    while q:
        now = q.popleft()
        if now == G:
            return visited[G] - 1
        val1 = now + U
        val2 = now - D
        if val1 <= F and not visited[val1]:
            q.append(val1)
            visited[val1] = visited[now] + 1

        if val2 > 0 and not visited[val2]:
            q.append(val2)
            visited[val2] = visited[now] + 1

    return "use the stairs"

F, S, G, U, D = map(int, input().split())
if (S > G and D == 0) or (S < G and U == 0):
    print("use the stairs")
    exit()

print(bfs())

cpp 풀이

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

int bfs(int _F, int _S, int _G, int u, int d) {
    vector<bool> visited(_F + 1, false);
    visited[_S] = true;

    queue<int> q;
    q.push(_S);
    int cnt = 0;

    while (!q.empty()) {
        int n = q.size();
        while (n--) {
            int val = q.front();
            if (val == _G) {
                return cnt;
            }
            q.pop();


            int up = u + val;
            int down = val - d;
            if (up <= _F && !visited[up]) {
                q.push(up);
                visited[up] = true;
            }
            if (down >= 1 && !visited[down]) {
                q.push(down);
                visited[down] = true;
            }
        }
        cnt++;
    }
    return -1;
}


int main() {
    int F, S, G, U, D;
    cin >> F >> S >> G >> U >> D;
    int result = bfs(F, S, G, U, D);
    if (result >= 0) cout << result;
    else cout << "use the stairs";
    return 0;
}