2331번

2331번 - 반복 수열

이번 문제는 재귀적인 방법으로 문제를 풀었다. BFS로도 풀 수 있을 것 같다.(코드 올림)

약간 DFS에서 노드를 방문하는 것처럼 그 다음 노드를 방문하는 방식으로  처음에 문제를 풀었다. 

 (사실 문제를 풀때는 노드 방문이라고 생각 안하고 그냥 재귀로 풀었다.)

범위가 N이 9999 이고 P 가 5이기 때문에 최대치 9999 랑 5 를 이용한 값을 구해도 300000이 넘지 않는다는 것을 알았다.

그래서 check 함수를 써서 방문한 곳과 방문하지 않은 곳을 찾아냈다.

방문 하지 않았다면 방문했다는 표시로 바꿔주고 다음 노드의 값을 계산한다.  그리고 vector 에 넣어준다.

이 때도 최대 6자리 이하라는 것을 알았기 때문에 for문에 들어간 방식처럼 할 수 있었다. 그래서 그 다음 노드를 DFS 에 다시 넣어준다. 

하지만 만약 이미 방문한 노드라면 다시 반복된다는 뜻이기 때문에 그 값을 same 값으로 해줬다.

그리고 값을 찾았다면 지금까지 저장된 vector 함수에서 몇번째 값인지를 찾아낸다.

재귀가 DFS 이기 때문에 뭐...

<정답 코드 - DFS >

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
 
bool check[300000];
int N, P;
int ans;
int same;
vector<int> v;
void dfs(int n)
{
    if (check[n] == false)
    {
        check[n] = true;
        v.push_back(n);
        int next = 0;
 
        for (int i = 100000; i >= 1;)
        {
 
            int x = 1;
            int mul = n / i;
            n = n % i;
            for (int j = 1; j <= P; j++)
            {
                x *= mul;
            }
            next += x;
            i /= 10;
        }
 
        dfs(next);
 
    }
    else
    {
        same = n;
    }
 
    
}
int main()
{
    memset(check, false, sizeof(check));
 
    cin >> N >> P;
 
    dfs(N);
    int ans = 0;
 
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == same)
        {
            break;
        }
        ans += 1;
    }
 
    cout << ans << endl;
 
    
 
 
    return 0;
}

<정답 코드 - BFS>

#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
 
int main()
{
    bool check[300000];
    int N, P;
    int ans=0;
    int same;
    vector<int> v;
 
    memset(check, false, sizeof(check));
 
    cin >> N >> P;
 
    queue<int> q;
 
    q.push(N);
    check[N] = true;
    v.push_back(N);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        //다음 값 구하기
        int next = 0;
        for (int i = 100000; i >= 1;)
        {
 
            int x = 1;
            int mul = now / i;
            now = now % i;
            for (int j = 1; j <= P; j++)
            {
                x *= mul;
            }
            next += x;
            i /= 10;
        }
 
        //다음 값 큐에 넣기
        if (!check[next])
        {
            q.push(next);
            v.push_back(next);
            check[next] = true;
        }
        else
        {
            same = next;
        }
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == same)
        {
            break;
        }
        ans += 1;
    }
 
    cout << ans << endl;
 
    
 
 
    return 0;
}