[DFS] 중복 순열

문제 유형

1번 부터 n까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 m번을 뽑아 일렬로 나열하는 방법을 모두 출력한다.

여기서 키워드 중복을 허락 , 일렬로 나열에 집중해야 한다. 일렬로 나열은 순열을 의미하고, 중복을 허락함으로써 중복 순열이 되기 때문이다.

필요자료구조

int n // (구슬 갯수),
int m // (뽑는 횟수),
int pm[] // (수열 값을 담는 배열),
int L // (현재 레벨),
DFS() 메서드 // 핵심 로직

핵심 문제 해석

1. 먼저 순열에 대해 이해해야 한다.
   순열은 n개의 원소들중 r개를 뽑아서 일렬로 나열하는 것이다.
   이를 공식화하면 nPr이 된다.
   nPr은 n!/(n-r)!을 의미한다. 또한,
   n>r 조건을 만족해야 한다.
   
   
   예를 들어, 구슬의 갯수가 3(n)이고 뽑기 횟수가 2(m)이라면
   3!/1!이다. 이를 조금 더 풀어본다면
   (3x2x1)/1이다. 즉 6가지의 경우의 수가 가능하다.
   
   
   현실에선, 1박2일에서 주로 하던 게임을 예시로 들 수 있다. 만약 5가지의 음식을 제작진이 준비했는데,
   출연진들이 게임에서 질 때마다 음식 하나를 빼야하는 게임이다. 그러면 처음에는 음식이 5가지가 존재한다.
   그런데, 출연진들이 게임에서 3연속으로 져서 3개의 음식을 빼야하는 상황이 발생했다면
   
   
   첫번째 음식을 반납할 경우의 수는 5
   첫번째 음식을 반납할 경우의 수는 4
   첫번째 음식을 반납할 경우의 수는 3
   이기 떄문에 이를 공식화 하면 5x4x3이다.
   
   
   이는 n!/(n-r)!과 같은 의미를 가진다.
   
   
   그렇다면 중복을 허용하는 순열은 어떻게 다를까?
   중복을 허용하는 순열은 제곱으로 바라보면 된다.
   
   
   예를들어, 문제에서 3개의 구슬 수와 3번의 뽑기 횟수가 가능하다면 3^3의 경우의 수를 가질 수 있게 된다.
   
   
   이를 일렬로 나열했을 때 아래와 같이 출력된다.

   1 1 1
   1 1 2
   1 1 3
   1 2 1
   1 2 2
   ...
   3 3 1
   3 3 2
   3 3 3

핵심 코드

public void DFS(int L){
	if(L == m){
    	for(int x : pm) System.out.print(x + " ");
            System.out.println();
        }
    }else{
    	for(int i = 1; i <= n; i++){
                pm[L] = i;
                DFS(L+1);
        }
    }
}

pm 배열이 초기화되는 과정을 스택프레임으로 이해하면 명확하게 이해할 수 있다.

1,1이 출력되는 스택 프레임은 아래 이미지와 같다.

아래 이미지는 DFS 알고리즘을 그래프 형식으로 그린 이미지다.

개선된 점

• 스택프레임으로 알고리즘 과정을 그려보면서 이해하기

피드백, 개선할 점

1. 이번 문제는 처음보는 문제 유형이었다. 30분 이상을 고민해보기는 했지만, 배열을 생성하는 부분과, 알고리즘을 설정하고 구현하는 부분에서 막혀서 정답 코드를 참고했다.
   
   
   결국 많이 풀어봐야 한다
   
   
   모르는 문제는 언제나 나올 수 있고, 그 문제 풀이에 계속해서 시간을 투자하는 것 또한 비효율적이기 때문에 정답 코드를 참고해야 하는 타이밍을 효율적으로 선택하는 것이 좋을 것 같다.

느낀점

• 모르는 문제를 마주하는 순간이 앞으로도 많을텐데
  효과적으로 문제에 접근하고 풀이하는 방법을 고민해봐야할 것 같다.
  
  

• 의심하지말자, 인내하자, 포기하지말자!
  문제 풀이가 막혀서
  
  
  "나는 왜 이렇게 멍청할까..", "내가 이 문제를 풀 수 있을까?"
  라는 생각이 들면서 스스로를 의심했는데,
  
  
  "문제를 풀 때까지 일어나지 말자!", "포기하지 말고 계속 나아가자!"라고 생각하며 문제를 풀었던 것 같다.