BOJ - 15649 N과 M(1)

1. 문제 : https://www.acmicpc.net/problem/15649

2. 문제 유형 : 백트래킹 알고리즘

3. 문제 티어 : 실버3 

4. 개념 학습

1) 백트래킹이란?
백트래킹(backtracking)은 모든 경우의 수를 탐색하면서, 조건에 맞지 않는 경우에는 중간에 탐색을 포기하고 돌아가는 방법. 즉, 안되는 길은 가지 않고, 될 가능성이 있는 길만 계속 탐색하는 알고리즘이다.

 

보통 재귀 호출을 사용하며, 탐색의 효율성을 높이기 위해 조건에 맞지 않는 경우를 빠르게 배제하는 것이 핵심이다.

 

2) 백트래킹의 동작 원리
 1. 결정 트리 탐색 :
    - 가능한 선택지를 하나씩 시도하며 트리 형태로 탐색한다.

 2. 조건 만족 여부 확인: 
    - 특정 조건에 부합하지 않으면, 더 깊이 탐색하지 않고 돌아간다.

 3. 되돌아가기(백트래킹) : 
    - 한 선택을 완료했거나 조건에 맞지 않으면, 이전 상태로 돌아가 다른 선택을 시도.

 

3) 대표적인 백트래킹 문제 유형
  - 순열
  - 조합
  - 미로 탐색
  - N-Queen 문제
  - 수열 생성 문제 

 

5. 문제 풀이

 1) 숫자를 선택하며 수열을 확장: 
   - 1부터 N까지의 숫자를 하나씩 선택하며 수열을 만든다.
   - 이미 선택된 숫자는 제외한다. => visited 등으로 방문 처리 필수! 

 2) 종료 조건 : 
   - 현재 수열의 길이가 M이 되면 수열을 출력.

 3) 백트래킹 : 
   - 재귀 호출 이후에는, 선택했던 숫자를 제거하고 방문 여부를 초기화하여 다음 숫자를 시도한다.

 

=> 핵심은 재귀 호출로 가능한 모든 수열을 탐색하는 것, 그리고 중복 체크를 위해 visited 배열, 수열 복구를 위해 current.pop() 등으로 이전 상태로 돌아가는 로직이 필요하다.

 

6. 정답 코드 

// 1. 값 입력받기
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [N,M] = input[0].split(" ").map(Number);

// 2. 방문 여부와 결괏값 담을 배열
let visited = new Array(N+1).fill(false);
let arr = [];

// 3. 재귀 함수를 사용한 백트래킹 알고리즘 작성
function recursive(current, visited , n,m){
    if(current.length === m) {
        console.log(current.join(" ")); // 공백을 넣어 하나의 문자열로 반환함
        return;
     }
     
     // n 만큼 반복문 순회
     for(let i=1;i<=n;i++){
         // 만약 방문하지 않았다면
         if(!visited[i]){
             // 방문 했음을 알려주고 값을 push 해줌
             visited[i] = true;
             current.push(i);
             
             // 한 번 더 다음 단계 탐색
             recursive(current, visited, n , m);
             // 이전 단계로 돌리기 위해 current.pop() 
             current.pop();
             // 다시 방문 처리 X
             visited[i] = false;
            }
       }
  }
  
  recursive(arr, visited , n , m);

 

 

7. 시간 복잡도

N ^ N ; 중복이 가능, N이 8일때 까지만 가능하다.  => 40320번까지 가능