인프런 커뮤니티 질문&답변

안녕하세요 stark님ㅎㅎ

일단.. 이 코드요 조금 다듬어 봤는데요. 다음과 같습니다.

로직은 맞는 것 같습니다. 좋은 아이디어네요.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 200004

int n, m, ret, visited[MAX], dx[3] = { -1, 1, 2 }; 
vector<vector<int>> trace(MAX);

bool Cango(int x)
{
    if (x < 0 || x >= MAX) return false;
    return true;
}

void BFS(int here)
{
    visited[here] = 1;
    trace[here].push_back(here);
    queue<int> q;
    q.push(here); 
    while (!q.empty())
    {
        int x = q.front(); q.pop();

        if (x == m)
        {
            ret = visited[x];
            break;
        }

        for (int i = 0; i < 3; ++i)
        {
            int next = 0; 
            if (i == 0 || i == 1) next = x + dx[i];
            else next = x * dx[2];  
            if (Cango(next) == false) continue;  
            if (visited[next] == 0)
            {
                visited[next] = visited[x] + 1; 
                q.push(next);
                // 이렇게 하면 더 간결합니다. 
                for(int i : trace[x]){
                    trace[next].push_back(i);
		} 
                trace[next].push_back(next); 
            }
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    if (n == m){
    	// 이렇게 해도 됩니다.  
        puts("0");
        return 0;
    }
 
    BFS(n);
    ret = visited[m] - 1;
    cout << ret << endl;
    for(int i : trace[m]) cout << i << " ";  
    return 0;
}

다만, 이렇게 코드를 짜면요. 공간복잡도가 터져서 틀린게 아닐까 생각이 듭니다.

자, 예를 들어

10만에서 0을 찾아가는 최악의 경우를 생각해볼게요.

10만 사이의 최적의 경로는 1개이지만,

stark님의 코드를 보면

99999에는 2개...

99998개에는 3개...

0에는 10만 1개의 원소가 저장되어야 하는 셈이죠.

즉, 10만 1개까지의 등차수열의 합이니까..

5,000,050,000

이정도의 숫자의 공간이 필요하게 됩니다.

즉, 50억 수준의 공간이 필요하게 되서 안되는 것 같습니다.

하지만 발상 자체는 너무나도 좋고, trace를 배우지 않은 상태에서 이런 발상을 생각해내셨다는 것은 정말 칭찬할 만합니다. ㅎㅎ 잘짜셨어요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.