[프로그래머스, 42839번] 소수 찾기 (DFS, Java)

문제설명

입력 & 출력

나의 풀이

이번 "프로그래머스 - 소수 찾기" 문제는 문자열로 주어진 숫자들로 조합하여 만들 수 있는 모든 수 중에서 소수를 찾는 문제입니다.

 

제가 풀이한 방법은 DFS 알고리즘을 사용하여 소수를 체크해주고, 소수 판별 함수를 만들어 해당 숫자가 소수인지 확인하는 방식으로 구현했습니다.

[Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)

전체 코드

 

DFS 함수

DFS 함수에서는 재귀를 사용하여 가능한 모든 조합을 탐색합니다. 백트래킹(Backtracking) 기법을 활용하여 불필요한 탐색을 줄이면서 숫자 조합을 생성합니다. 또한 중복을 없애기 위해 Set 리스트에 담아줍니다.

• 각 문자를 선택하고, 그 선택을 기준으로 다음 단계로 넘어갑니다.
• 선택한 문자를 now 문자열에 추가하여 새로운 숫자를 생성합니다.
• 백트래킹(Backtracking)
  • 탐색이 끝난 후, 방문 상태를 초기화(visited[i] = false)하여 다음 탐색에 영향을 주지 않도록 합니다.
  • 이렇게 하면 이미 탐색한 경로를 제외하고 다른 조합을 탐색할 수 있습니다.

---

예제 입력 : numbers = "011"

 

0.초기 상태 

• now = "" (현재 조합 없음)
• depth = 0 (탐색 깊이 0)
• visited = [false, false, false] (모든 숫자는 아직 방문되지 않음)

1. 첫 번째 DFS 호출 : dfs(numbers, 0, "")

• i = 0
  • now = "" + numbers.charAt(0) : "0" ➡️ now = "0"
  • visited = [true, false, false] (첫 번째 숫자 방문 처리)
  • 재귀 호출: dfs(numbers, 1, "0")

2. 두 번째 DFS 호출 : dfs(numbers, 1, "0")

• i = 1
  • now = "0" + numbers.charAt(1) : "1" ➡️ now = "01"
  • visited = [true, true, false] (두 번째 숫자 방문 처리)
  • 재귀 호출: dfs(numbers, 2, "01")

3.세 번째 DFS 호출 : dfs(numbers, 2, "01")

• i = 2
  • now = "01" + numbers.charAt(2) : "1" ➡️ now = "011"
  • visited = [true, true, true] (세 번째 숫자 방문 처리)
  • 조합 완료 → set.add(11)
  • 재귀 호출: dfs(numbers, 3, "011")  ➡️ depth == numbers.length() 종료 조건에 도달 : 탐색 끝
  • 백트래킹 → visited[2] = false

탐색을 완료한 후에는 다시 이전 단계로 돌아가서 다른 경로를 탐색해야 합니다. 여기서 백트래킹이 이루어집니다.

• depth == 3 (탐색 끝), visited[2]를 false로 되돌려서 2번 인덱스 (숫자 "1")를 다시 선택할 수 있도록 합니다.
•  이제 다시 이전 단계 (depth = 2, now = "01")로 돌아갑니다.
• 백트래킹 후 상태
  • now = "01", visited = [true, true, false]

4.이전 단계로 돌아가기 : dfs(numbers, 1, "0")

• 현재 상태: now = "0", depth = 1, visited = [true, false, false]
• 이전에 선택하지 않았던 숫자를 선택하여 새로운 조합 생성.
• visited[1] = true로 선택된 숫자 1은 더 이상 선택할 수 없으므로, 다시 i = 0부터 반복문을 실행하여 다른 경로를 탐색하려고 할 수 있습니다.

5.다른 경로 탐색

 

여기서 중요한 점은 백트래킹을 통해 방문 처리된 숫자를 되돌려 놓고, 새로운 경로를 탐색하는 것입니다. 이 과정은 특정 숫자를 한 번 더 선택하거나, 다른 숫자를 선택하는 방식으로 진행될 수 있습니다.

 

 

소수 여부 판별 함수 (isPrime)

 

[Algorithm] 효율적인 소수 판별: 기본 방법부터 에라토스테네스의 체까지

 

위 포스팅에서 알아본 것 처럼 효율적인 계산을 위해 Math.sqrt() 메서드를 사용하여 제곱근까지 반복을 해주면서 소수를 구해줍니다.