문제 148653. 마법의 엘리베이터

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/148653

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

+10^n 또는 -10^n로 이동하는 엘리베이터가 있습니다. (n은 0이상의 자연수)엘리베이터를 이동시키기 위해선 마법의 돌이 필요하며, 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다. 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요. 

입력

• 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey

입력 제한

• 1 ≤ storey ≤ 100,000,000

입력 예제

// input
16

// ans
6

 

풀이 방식

이 문제는 1차원 bfs문제라고 판단하여 bfs를 활용하여 문제를 풀었다. 0층을 최소한의 이동으로 이동하는 것이 목표이기 때문에 한 번 방문한 층을 더 이상 방문하지 않도록하고(다시 방문했다는 것은 이미 최소한의 이동이 아니기 때문), 0층을 찾을 때까지 새로운 층을 찾는 과정을 반복한다. 해당 과정을 반복하여 0층을 찾았다면 이동한 최소횟수 반환하면 정답이 된다.

 

0층을 못찾는 경우는 왜 언급이 없을까?

이런 문제들은 대게 해당 층을 찾지 못했을 때 -1을 출력하라는 등의 추가 요구 사항이 있기 마련인데, 이 문제는 이런 요구 사항이 없는 것을 볼 수 있다. 그 이유는 이 문제에서만큼은 어떤 상황에서도 0층을 갈 수 있기 때문이다. 마법의 엘레베이터는 +-10^n으로 이동한다 즉, +1 또는 -1만큼도 이동할 수 있다는 것을 의미한다. 따라서, 1칸씩 위로 또는 아래로 이동할 수 있기 때문에 갈 수 없는 층은 존재하지 않아 못찾는 경우에 대한 언급 또한 없다.

정답 코드 

#include <string>
#include <vector>
#include <queue>

#define MAXN 100'000'000

using namespace std;

vector<bool> visited;

struct pos_data{
    int x;
    int cnt = 0;
};

bool inRange(int x) {
    return 0 <= x && x <= MAXN;
}

int bfs(int storey){
    queue<pos_data> q;
    
    q.push({storey, 0});
    visited[storey] = true;
    
    vector<int> dx;
    
    for(int i = 1; i <= MAXN; i*=10){
        dx.push_back(i);
        dx.push_back(-i);
    }
    
    while(!q.empty()){
        pos_data cur_pos = q.front(); q.pop();
        
        for(int i = 0; i < dx.size(); i++){
            int nx = cur_pos.x + dx[i];
            
            if(inRange(nx) && !visited[nx]){
                if(nx == 0) return cur_pos.cnt + 1;
                q.push({nx, cur_pos.cnt + 1});
                visited[nx] = true;
            }
        }
    }
}

int solution(int storey) {
    int answer = 0;
    visited.resize(MAXN+1);
    
    answer = bfs(storey);
    
    return answer;
}