[BFS/Stack]백준2331번 반복수열

백준 2331

반복되지 않는 수의 개수를 찾아야 한다.

dfs로 풀 수 있는 문제로 분류되어 있었는데, DFS를 어떻게 활용해야 할 지 몰라 BFS와 stack을 이용했다.

우선 수열에서 다음 항을 찾기 위한 방법은 다음과 같다.

int makeD(int n){
    int sum = 0;
    int target = n;
    while(target!=0){
        sum += pow(target%10,exponential);
        target /= 10;
    }
    // cout << sum;
    return sum;
}

함수를 만들어 사용했는데, 매개변수로 받은 n을 10으로 나눈 나머지를 P 승 해준 것을 누적하며 더하고, n은 계속해서 10으로 나눠간다. 이러면 맨 끝 1의 자리부터 합을 구해갈 수 있다.

BFS는 다음과 같은 방식으로 동작한다.

queue의 front 에 위의 함수를 실행한 결과를 받는다.

실행한 결과가 전에 나왔던 수인지 본다.

만약 방문한 적이 없다면 (visited==0)

• queue에 넣어 다음에 방문한다.
• stack에 push 한다.
• visited 를 ++ 한다.

만약 전에 한 번 방문했었다면 (visited==1)

• queue에 넣어 다음에 방문한다.
• stack을 pop 한다.
• visited를 ++ 한다.

만약 반복수열이 생겨 한 번 반복되면, 더 이상 queue에 담기지 않기 때문에 BFS가 종료된다.

이 때 반복되는 횟수만큼 stack에서 pop 했기 때문에 stack 의 밑에 있었던 반복되지 않는 수들만 남았다.

stack의 size를 출력한다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;
 int num,exponential;
int visited[1000000] = {0,};
int main(){
    cin >> num >> exponential;

    queue<int> q;
    stack<int> s;
    visited[num]++;
    q.push(num);
    s.push(num);
    int makeD(int n);

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        // cout << cur << endl;
        int tmp = makeD(cur); 
        if(visited[tmp]==0){
            visited[tmp]++;
            q.push(tmp);
            s.push(tmp);
        }
        else if(visited[tmp] ==1){
            q.push(tmp);
            visited[tmp]++;
            s.pop();
        }
    }
    cout << s.size() << endl;
}
int makeD(int n){
    int sum = 0;
    int target = n;
    while(target!=0){
        sum += pow(target%10,exponential);
        target /= 10;
    }
    // cout << sum;
    return sum;
}