[BOJ][2331] 반복수열

1. 문제 링크

https://www.acmicpc.net/problem/2331

2. 사용 알고리즘

DFS

3. 풀이

• 문제에 주어진 A부터 DFS 탐색을 하며, 몇 번째로 방문한 정점인지 count 저장

• 해당 정점이 이미 방문한 정점인 경우 → count - 1 리턴

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/2331.cpp

#include <iostream>

using namespace std;

int check[333333];

int next(int num, int p) {
    int ret = 0;
    while(num != 0) {
        int temp = 1;
        for(int i = 0; i < p; ++i) temp *= (num % 10);
        ret += temp;
        num /= 10;
    }
    return ret;
}

int solve(int num, int p, int cnt) {
    if(check[num]) return check[num] - 1;
    check[num] = cnt;
    int temp = next(num, p);
    return solve(temp, p, cnt + 1);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int a, p; cin >> a >> p;
    cout << solve(a, p, 1) << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/2331.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    static int check[] = new int[333333];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        System.out.println(solve(a, p, 1));
    }

    public static int next(int num, int p) {
        int ret = 0;
        while(num != 0) {
            int temp = 1;
            for(int i = 0; i < p; ++i) temp *= (num % 10);
            ret += temp;
            num /= 10;
        }
        return ret;
    }

    public static int solve(int num, int p, int cnt) {
        if(check[num] != 0) return check[num] - 1;
        check[num] = cnt;
        int temp = next(num, p);
        return solve(temp, p, cnt + 1);
    }
}