Algorithm [3] - 가위바위보

문제

가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서
한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 
한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 가위바위보 게임의 수를 나타내는 정수
rounds 가 주어질 경우, 해당 rounds 동안 선택할 수 있는 모든 경우의 수를 구하세요.

입력

인자 1 : rounds

• Number 타입의 양의 정수

출력

• 최종적으로 리턴되는 배열의 순서는 가중치 적용 정렬(Weighted Sort)을 따릅니다.
• 중요도는 'rock', 'paper', 'scissors' 순으로 높습니다.

입출력예시

let output = rockPaperScissors(5);

console.log(output);
/*
    [
      ["rock", "rock", "rock", "rock", "rock"],
      ["rock", "rock", , "rock", "rock", "paper"],
      ["rock", "rock", , "rock", "rock", "scissors"],
      ["rock", "rock", "rock", "paper", "rock"],
      ["rock", "rock", "rock", "paper", "paper"],
      ["rock", "rock", "rock", "paper", "scissors"],
      ["rock", "rock", "rock", "scissors", "rock"],
      // ...etc ...
    ]
  */

수도코드

1. 임의의 rounds가 주어졌으니 재귀를 사용한다.
2. 중요도순으로 배열을 정렬한 후 시작한다.
3. 스택쌓기와 재귀, 반복을 이용해서 모든 경우의수를 가져온다.

문제풀이

const rockPaperScissors = (rounds) => {
  rounds = rounds || 3;

  const arr = ["rock", "paper", "scissors"];  
  const result = [];

  let game = (round, resultArr) => {
    if(round === 0){
      result.push(resultArr); 
      return;
    }

    for(let i = 0 ; i < arr.length ; i++){ 
      let current = arr[i];
      game(round-1, resultArr.concat(current))
    }
  }

  game(rounds, []); 

  return result;
}

코드해석

일단 주어진 인자를 인식해야한다, 인자로 추가된 rounds가 존재한다면 rounds 인자를 사용하고
rounds가 존재하지 않다면 최솟값의 3을 인자로 사용한다. 기존의 문제에서 수정한부분이 있어서
이 부분이 존재하지만, 문제푸는데에는 지장이 없으므로 넘어가도록 한다.

그리고 중요도에 따라 가위바위보를 정렬한 배열을 생성한다. 이것이 모든 계산의 베이스가 된다.

최종적으로 2차원적 배열로 생성될 1차원배열 result를 만들어주고,
앞으로 만들어질 배열들이 여기에 들어올것이다.

재귀를 시작한다, 인자는 두개를 받아온다. 기존에 인자로 받아온 rounds와 빈배열이다.
주어진 게임의 수를 모두 소모할때까지 재귀를 진행하고, 그 안에서도 반복을 진행할것이다.

일단 재귀함수를 담을 game이란 변수를 만들어준다. 그리고 인자를 두개를 생성한다, 이름은 무관하다.

재귀의 첫번째조건 -> 재귀의 종료조건이 필요하다.
아까 말한것처럼 주어진 게임의 수를 전부 사용하면 재귀를 종료시켜야한다.
여기서는 round가 인자로 주어졌으므로, round가 0이되면 재귀를 종료하고 resultArr를 result에
담는다고한다. 아직 resultArr의 기능은 모르니 일단 이정도로만 파악하고 넘어간다.

그리고, 재귀의 두번째 조건 -> 재귀 종료조건에 접근하는 로직작성
어쨌든 재귀는 종료되어야 하고, 그럴 수 있게 반복이던지, 소모라던지, 어떠한 방법을 통해 재귀의 종료조건
에 접근해야한다, 여기서는 round의 소모로 재귀가 끝나는 로직이니 하나의 인자는 정해졌다.
'round - 1' 이 되야될것이고, 이제 아까 잠깐 나왔던 resultArr가 어떻게 생성되는지 살펴본다.

for문이 등장한다, 이 for문은 arr의 길이를 탐색한다. arr는 ["rock", "paper", "scissors"]로
총 길이 3, 여기서는 0,1,2 의 인덱스를 순회할것이다.

여기서 잘 살펴보면 재귀함수인 game이 반복문안에서 형성된걸 볼 수 있다. 이점을 주목해야 한다.
여기서의 코드진행을 보겠다, 맨 처음 round와 빈배열을 가지고 함수가 실행된다.
그리고 처음에 맞이한 종료조건에는 아직 해당되지 않으므로 다음 코드로 넘어간다.
여기서 for문을 맞이하고, arr[0] ('rock') 를 할당받은 current를 만난다.

그리고 재귀가 진행되는데, 그 인자로 round-1 과 resultArr.concat(current) 이 주어졌다.

**** 여기서 중요한점, 이때 반복은 0번째 인덱스에서 멈춘다, 왜냐하면 반복이 진행되기 전에
재귀가 진행되면서 스택이 쌓이고 새로운 game함수가 실행되었기 때문이다.
디버깅을 해보면 확실하게 알 수 있다, 콜스택의 리스트를 확인해보면 스택이 하나 더 쌓인것으로 볼 수 있다.
그렇다는것은 resultArr가 빈배열에서 이전 스택에서 받아온 arr[0] ('rock') 을 받아와서
resultArr = ['rock'] 인 상태로 다음 재귀를 진행하는것이다. 이때 round는 1이 감소되고
현재의 상태로 다시한번 재귀의 종료조건과 비교한다, 하지만 이 문제의 round의 최솟값은 3이기때문에
아직 최소 2번의 재귀가 더 남았음을 짐작할 수 있다. 그럼 다시 for문으로 넘어오게 된다.
현재의 for문은 아까 만났던 for문과 다른 코드이다,

이게 무슨말이냐면, 마블의 영화로 치면 멀티버스의 느낌이다. 첫번째 재귀함수가 실행되고 반복문을 만났고.
반복이 미처 진행되기 전에 재귀로 인해 한 스택이 쌓인 새로운 재귀함수를 만나게 된것이다. 그리고
현재 만나게 된 반복문은 이 새로운 재귀함수 안에 있는 반복문이기때문에, 이 반복문은 처음 실행되는
것이다. 그래서 아까와 동일하게 resultArr는 이 멀티버스의 arr[0]을 또 담게 된다.
그리고 다시한번 재귀를 만나고 또 다음 재귀함수로 넘어가게 된다. 또 다른 멀티버스를 만나게 되는것이다.

하지만 이 와중에서도 round는 계속해서 줄어들고 있을것이다. round를 3으로 받았다고 가정하고
진행해본다면, 이제 세번째 멀티버스를 만나 resultArr가 세가지의 rock을 모두 받고
['rock', 'rock', 'rock'] 으로 완성될것이다, 그리고 드디어 다음 멀티버스에서 round가 0이 된다.
그렇다면 이제 이 멀티버스에서 탈출할 수 있게 되었다. 네번째 재귀에서 종료조건을 만나게 된다.

이제 종료조건에 맞게 되어서 resultArr를 result에 담아주고 해당 재귀를 종료하게 된다.

자, 이제 어떻게 될까? 바로 이전의 멀티버스로 되돌아가게 된다. 이전스택으로 되돌아가는것이다.
언제로? 세번째 멀티버스(스택)의 arr[0]를 받기 전으로 되돌아가는것이다.

세번째 스택의 arr[0]를 받은 함수는 종료조건에 맞아 종료되었으니, 그 스택은 사라지게 된다.
그럼 그 스택에 밑에 있던 반복문이 잠깐 멈춰있다가 다시 실행이 되는것이다.
이제 arr[1]로 인자를 넘기게 될것이고, 다시 그걸받은 resultArr 와 또다시 재귀를 실행하게 된다.
그럼 또 바로 다음 재귀에서 종료조건에 맞아 result에 넣어주고 재귀를 끝내게 된다.

이런식으로 세번의 반복이 진행되어 세번째 멀티버스의 모든 반복이 끝나게 되면, 반복이 종료됬으므로
해당 스택, 멀티버스가 자연스럽게 종료되게 된다. 그럼 어떻게 되는가? 이제 그 밑에 있는
두번째 멀티버스로 넘어가는것이다. 정말 어지럽다.. 내가 지금 쓰면서도 맞나 싶을정도로 어지럽다.
이런식의 반복이 진행되는것이다, 스택을 쌓고, 그 안에서 반복이 진행되고, 재귀가 진행된다.

결국 3가지의 요소를 3가지의 갈래로 나뉘어 반복이 진행된다. 3차원의 반복이라고 보면 될것같다.

이 다음도 보면 두번째 멀티버스의 첫번째 인덱스에서 두번째로 넘어간다는것은 첫번째 인덱스에 해당된
멀티버스가 전부 종료됬다는것을 의미한다. 그리고 두번째로 넘어가서 다시 같은 반복을 진행하게 되는데
여기서 다시 세번의 반복이 진행되고 .. 진행되고.. 말로는 도저히 풀어낼 수 없다.

아무튼 내가 말로 설명할 수 있는 최선을 다했다. 이런 개념이다. 찬찬히 읽어보면 대충 감은 올것이다.

마지막으로 저 모든 반복을 거쳐서 결과값을 담은 result를 리턴하면 모든 식이 종료된다.