[백준] 2331번 반복수열 (DFS_Java)

굴러라 굴러 코테 공장!

 

DFS를 정복하기 위해

백준 실버문제부터 다시 차근차근 풀어보고 있다.

 

---

문제

 

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

2331번: 반복수열

 

 

---

설계

 

알고리즘 설계 [접근 방법] : DFS

숫자가 주어지면, 그 숫자를 한자리 수만큼 쪼갠 후 P만큼 제곱해서 더한 값을 다시 쪼개고 제곱하고..

무한반복으로 이루어지는 과정에서, 이미 앞서 나온 값이 있다면 종료하는 문제다.

 

여기서 주요한 점은, 만약 37이 앞에 나왔다면 37 이후에 나온 모든 값들은 중복수열에 포함된다는 것이다. 나는 map을 활용하여 중복을 체크하고 DFS로 계산을 해주었다.

 

풀이 과정

1.

 최초 값 a, 제곱수 p를 입력받는다.

나는 여기서 편하게 계산하기 위해 a를 String으로 입력받았다.

 

2.

중복체크를 할 map을 생성한다.

 

3.

DFS 메서드에서는 String으로 된 숫자를 한 자리씩 char 형태로 자른다.

그 후 p만큼 제곱한 수를 result에 더한다. 그리고 이 값을 다시 String으로 변환한다.

 

4.

map에 이미 존재하는 숫자라면, 그 숫자의 value값을 false로 변경한다. 여기서 바로 return하지 않는 이유가 있다.

만약 map에 37, 58...이 존재하고 이번에 37이 되돌아 왔다. 이 상황에서 return을 한다면 58의 값은 true로 남아있게 된다. 58이 true로 DFS가 모두 종료된다면 중복 수열로 체크가 되지 않는다. 그래서 나는 37, 58.. 이후에 37번이 다시 오게되었다면, 이번은 그냥 값을 false로만 바꾸고 다시 DFS를 진행한다.

 

5.

map에 이미 존재하는 숫자이면서, 그값이 false라면 이미 숫자가 2번 반복되었다는 뜻이다. 중복 수열은 이미 false로 변경되었을 것이다. 그럼 DFS 종료한다.

 

6.

만약 처음 계산된 숫자라면, map에 값을 true로 저장한다.

그리고 DFS를 실행한다.

 

 

---

코드

 

import java.util.*;

public class Test_2331_반복수열 {
	
	static Map<String, Boolean> map;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.next();		//최초 값
		int p = sc.nextInt();		//제곱수
		
		//반복수열을 저장할 map
		map = new HashMap();					
		
		//DFS 실행
		map.put(a, true);
		DFS(a, p);
		
		//반복수열 제외 개수 세기
		int answer = 0;
		for(String str : map.keySet()) {
			if(map.get(str)) answer++;
		}
		
		//출력
		System.out.println(answer);
	}
	
	//DFS
	public static void DFS(String a, int p) {
	
		//계산하기
		int result = 0;
		char[] chArr = a.toCharArray();
		for(int i=0; i<chArr.length; i++) {
			result+=Math.pow(chArr[i]-'0', p);
		}
		
		String str = String.valueOf(result);
		
		//이미 존재하는 숫자인데, 다시 왔다면
		if(map.containsKey(str) && map.get(str)) {
			map.put(str, false);
			DFS(str, p);
		}
		
		//이미 존재하는 숫자인데, 2번 다시 왔다면
		else if(map.containsKey(str) && !map.get(str)) {
			return;
		}
		
		//새로운 숫자라면,
		else if(!map.containsKey(str)) {
			map.put(str, true);
			DFS(str, p);
		}	
	}
}

 

 

(❁´◡`❁)

끝!