프로그래머스 콜라츠 추측 (DFS 파이썬 풀이)

• 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12943

프로그래머스

 

• 다른 사람들의 풀이 

#  - , - , - , 강준기 , - 외 7 명 님 코드 참고
def collatz(num):
    for i in range(500):
        num = num / 2 if num % 2 == 0 else num*3 + 1
        if num == 1:
            return i + 1
    return -1

 

 

• 내 DFS 풀이

def dfs(num,cnt):
    if cnt > 500 : return -1
    if num == 1:
        return cnt
    else:
        cnt += 1
        if num % 2 == 0:
            num = num // 2 
        else:
            num = (num * 3) + 1
    return dfs(num, cnt)

def solution(num):
    answer = 0
    return dfs(num,answer)

 

 

• 해설

솔직히 이문제는 DFS 로 풀필요가 없다 단순하게 최대 500번만 반복하기 때문에 일반적인 for문으로도 충분히 가능한 문제이다. 하지만 DFS를 공부하고 있기 때문에 재귀로 한번 풀어보면 어떨까라는 생각에 풀어본 문제이다.

 

dfs 에서 중요한 종료조건을 500번 일때 -1 return 과 결국 num 이 1이 될 때 cnt 로 리턴 하는 방법으로 종료조건을 정했다.

 

재귀를 돌리기 위해서 dfs 함수에 cnt 변수와 들어온 num 의 변수를 더해서 연산을 재귀적으로 하여 결과값을 추출했다.