[C#] 프로그래머스 백트래킹 - 소수 찾기

1. 중복 방지를 위해 List<int>에서 .Contains(num)을 사용 / 중복 방지용으로 visited

2. 소수 판별 함수 구현

3. 모두 방문해 string으로 +하고 DFS 결과로 int count를 내보내기

using System;
using System.Collections.Generic;

public class Solution {
    List<int> foundPrimes = new List<int>(); // 중복 방지용 리스트

    // 소수 판별 함수
    public bool isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    // DFS 백트래킹 탐색
    public int DFS(string numbers, bool[] visited, string currentNumber) {
        int count = 0;

        if (currentNumber.Length > 0) {
            int num = int.Parse(currentNumber);
            // 중복되지 않은 숫자이고, 소수라면 카운트 증가
            if (!foundPrimes.Contains(num) && isPrime(num)) {
                foundPrimes.Add(num); // 중복 방지 리스트에 추가
                count++;
            }
        }

        for (int i = 0; i < numbers.Length; i++) {
            if (!visited[i]) {  // 방문하지 않은 숫자만 선택
                visited[i] = true;
                count += DFS(numbers, visited, currentNumber + numbers[i]);
                visited[i] = false;  // 백트래킹
            }
        }

        return count;
    }

    public int solution(string numbers) {
        bool[] visited = new bool[numbers.Length];

        // 백트래킹 시작
        return DFS(numbers, visited, "");
    }
}