백준 2331 반복 수열 dfs bfs

문제 링크

문제풀이

특정한 연산을 통해 수열을 생성하고, 반복된 숫자가 생성시 반복된 수열을 제외한 수열의 길이를 구하는 문제 였다. 재귀를 사용했기 때문에 넓게 보면 dfs를 사용한 것일 수도 있겠다.
문제가 특별히 어렵지 않았으나 이것저것 꼬여서 시간을 허비했다. 글을 쓰는 이유도 오늘을 기억하기 위해서다.
로직은 간단한다.
1. 메서드를 통해 각 자리수를 제곱하는 메서드를 만든다.
2. 리스트에 담아주고, 값을 맵(셋에 넣어주는게 더 낫다고 생각한다.)에 넣어준다.
3. 맵을 통해 중복된 값인지 확인해주고 재귀로 다시 처음부터 구한다.
4. 중복된 값이라면 리스트에서 인덱스를 구해줘 인덱스 값을 출력한다.

package argo.dfsAndBfs;
import java.util.*;
public class RepeatNumberCycle {

   static int base;
   static int power;
   static int count;
   static HashMap<Integer, Integer> mem;
   static ArrayList<Integer> a;
   
   public static void main(String[] args){
       
       Scanner sc = new Scanner(System.in);
       base = sc.nextInt();
       power = sc.nextInt();
       mem = new HashMap<>();
       a = new ArrayList<>();
       count = 0;
       a.add(base);
       mem.put(base,1);
           cal();


       System.out.print(a.indexOf(base));
   }
   static void cal(){
   	int tmp = base;
   	int sum =0;

   	while(true) {
   		sum += (int) Math.pow(tmp%10, power);
   		tmp = tmp/10;
   		if(tmp/10==0) {
   			sum += (int) Math.pow(tmp, power);
   			break;
   		}
   	}
   	base = sum;
       while(!mem.containsKey(base)){

           mem.put(base,1);
           a.add(base);
       
       cal();

       }
   }
}