프로그래머스 - N으로 표현

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

풀이 : Bfs를 이용한 완전탐색

class Solution {
    static int answer =-1;

    public int solution(int N, int number) {

        dfs(N, number, 0,0);
        return answer;
    }
    static void dfs(int N, int number , int cnt, int prev) {
        //N의 카운트를 늘려가며 dfs 로 수행한다. 
        //그 값을 저장하고 그 값이 number와 동일한지 확인한다. 
        int temp_N = N;
        if (cnt > 8) {
            answer = -1;
            return;
        }

        if (number == prev ) {
            if (answer == -1 || answer > cnt)
                answer = cnt;
            return;
        }

        for (int i = 0; i < 8-cnt; i++) {
            dfs(N, number, cnt+i+1, prev-temp_N);
            dfs(N, number, cnt+i+1, prev+temp_N);
            dfs(N, number, cnt+i+1, prev*temp_N);
            dfs(N, number, cnt+i+1, prev/temp_N);

            temp_N =  temp_N * 10 + N;
        }
    }
}