백준 15650 - N과 M (1)

재귀함수 + 백트래킹으로 푸는 문제

백트리캥이란?

메이플 퀘스트 같은거 할 때  npc한테 대화 걸어서 하나씩 다 누른다음에 결과 확인하고 - 뒤로가서 다시 다른거 누르고 - 다시 돌아오고 하는 거랑 비슷함

유식하게 풀어쓰면 모든 경우의 수를 다 살펴보는 알고리즘이라고 보면 됨

 

기본개념

1부터 4까지의 숫자 중 2개를 뽑는 경우( 중복 x ex)(1,1) )

할 수 있는 모든 경우의 수를 생각해보면 일단 제일 처음에 1을 뽑아서 배열에 넣고([1, ?])

+ 중복이 안되기 때문에 뽑은 숫자는 표시를 해줌

그 다음에 올 수 있는 수는 2,3,4 -> 여기서 2를 넣으면 ([1,2]) 2개를 이미 뽑았기 때문에 뒤에 들어온 2만 빼주고 다시 3,4 중에 다시 체크

-> 뺑뺑이 돌리면 됨

그런데 뭔가 비슷한 작업을 계속 하고있는게 보일거임(안뽑은 숫자 체크+숫자 넣어주기+다 뽑은 경우에 숫자 빼주고 체크표시 지우기..)

== 재귀쓰면 된다는 소리...

 

function recursion(k) {
  //숫자 n개중에서 m개 뽑는것
  if (k === m) {
    console.log(...arr);
    return;
  }
  for (let i = 1; i <= n; i++) {
    if (!isUsed[i]) {
      arr[k] = i;
      isUsed[i] = true;
      recursion(k + 1);
      isUsed[i] = false;
    }
  }
}

arr = 뽑은 숫자 넣어놓는 배열
isUsed = 숫자 사용여부 기록해놓는 배열 / index 0은 사용안하고 index 1 = 숫자 1
recursion 한번 실행될때마다 - 하나씩 arr에 넣고 다시 recursion(k+1) 실행 - 다 넣으면 리턴

 

 

3개 중 1개 뽑는 경우
recursion(0)으로 시작 
k값을 숫자 뽑는 순서?라고 생각하면 될듯 k=0이면 첫번째 숫자 뽑기,k=1이면 두번째....

- 반복문이 주어진 숫자 수만큼 반복문을 돌면서 재귀함수를 호출함(여기서는 1부터 3까지)

- isUsed[1] === false이기 때문에 arr[0] = 1 , isUsed[1] = true 

- recursion(1)을 호출함 (다음 수를 뽑음)

- k === m에 걸리기 때문에 return됨

- 이후 다시 안끝났던 반복문으로 돌아와서(이때 i = 1) isUsed[i] = false로 바꿔줌 

//arr = [1] , isUsed = [0,f,f,f]

 i=2일 때 시작 // k=0인거 주의
- arr[0] = 2 // isUsed[2] = true
- recursion(1) -> return
- isUsed[2] = false
 arr = [2] , isUsed = [0,f,f,f]
 i=3일때 시작 
- arr[0] = 3 // isUsed[3] = true
- recursion(1) -> return

recursion(0) // 1 2 3

 

중복 제거 안하고 싶으면 ? isUsed 빼버리면 됨