문제
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력하세요.
ex) 3 2를 입력할 시 N=3, M=2
코드
public class DoublePermutation {
static int[] pm;
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
pm = new int[m];
dfs(0);
}
public static void dfs(int level){
if(level == m){
for(int i : pm) System.out.print(i+" ");
System.out.println();
}else{
for(int i = 1; i<= n; i++){
pm[level] = i;
dfs(level+1);
}
}
}
}설명
지금까지 공부했던 dfs는 이진트리 형식으로 문제를 풀어낼 수 있었다. 하지만 현재 문제는 2가지 방향으로 뻗어나가는것이 아닌 3가지 방향으로 뻗어나가는 문제가 된다.
그러면 이럴땐 어떻게 풀어내야할까? dfs를 3번 호출해도 되겠지만 반복되는 것을 처리하는 것은 반복문으로 가독성 좋게 풀어내는 것이 현명하다. 만약 3번, 4번은 반복으로 dfs를 호출해서 적어낸다 해도 10가지 20가지로 뻗어갈 경우에도 똑같이 아니 뻗어나가는 경우가 조건에 따라 달라질때도 똑같이 할순 없으니 말이다.
그리고 해당 코드가 지금까지 해왔던 코드랑은 아주 조금 다르지만 이해하기 어려울수 있다. 그래서 같이 한번 스택과 트리를 그려가면서 구조를 같이 이해해보자!
지금까지 공부한 dfs코드와 반복문으로 처리되는 곳 말고는 거의 일치하기 때문에 dfs 로직에 대해서는 설명하지 않겠다.
dfs(0)
jvm
jvm에는 dfs(0)의 메서드가 존재하게되며 dfs(0) 내부 로직이 실행된다.
첫 조건문인
//m=2
if(level == m)조건에 만족하지 않으므로 else 로직이 실행된다.
for(int i = 1; i<= n; i++){
pm[level] = i;
dfs(level+1);
}else로직에는 pm[]에 값을 넣어주며 다음 dfs를 호출하는데 이때 i=1부터 실행된다.
pm[0] = 1;
dfs(0+1);을 실행할 수 있다. 그럼 이 때 pm[]배열과 트리를 확인해보자
i=1
pm 배열
1번 배열에 0이란 초기화 값이 있지만 이해를 돕기 위해 표현하지 않았다.
트리
dfs(0+1)은 다음 노드를 실행하는 것이므로 다음과 같이 표현되었다.
dfs 내부 로직을 모두 실행한 후 dfs(1)을 실행도 확인해보자.
dfs(1)
위에서 설명한 조건은 이제 설명하지 않겠다. 조건에 부합하지 않아 바로 반복문이 실행된다.
pm[1] = 1;
dfs(0+1);jvm
pm배열
트리
pm[1] = 1 이라는 값을 넣어준 뒤 dfs(2)를 실행시킨다.
dfs(2)
jvm
dfs(2)는 첫 조건에 만족한다.
//m=2
if(level == m)조건에 맞는 로직이 실행된다.
for(int i : pm) System.out.print(i+" ");
System.out.println();pm[0] pm[1]은 현재 {1,1}이므로 1 1이 결과값으로 출력되고 반환된다. 그럼 이때 jvm 내부에서는 dfs(2)가 반환되며 dfs(1)로 넘어가게되는데
jvm
dfs(1)의 코드이다.
for(int i = 1; i<= n; i++){
pm[level] = i;
dfs(level+1);
}dfs(1)은 dfs(2)의 값은 반환 받았지만 아직 반복문이 종료되지 않았다. 그래서 i의 다음값인 i가 2일때가 실행된다. 이걸 트리로도 확인해보면
다음과 같이 동작된 것을 확인할 수 있다.
i=2
pm[1] = 2;
dfs(1+1);의 코드가 실행되어지며
pm 배열
pm[1] = 2 값을 넣고 dfs(2)를 다시 호출한다.
jvm
그럼 좀 전에 위에서 했던 실행이 그대로 반복되며
1 2를 프린트한 후 반환받고
jvm
다시 i는 증가하며
트리
노드를 실행시키는 것을 확인할 수 있다.
i=3
이제 여기 부분은 이해했을 거라 믿고 결과 확인한 뒤 다음 실행을 계속 봐보자.
i가 3일때 동일하게 dfs(2)가 실행되어
1 3
을 출력한 뒤 반복문이 종료된다.
우리가 지금까지 살펴본 dfs(1)의 반복이 종료되어 반환을 하게 되면 dfs(0)으로 돌아가게 되어 dfs(0)의 남은 반복문을 다시 실행하게 된다. 그러면 다시 dfs(1)을 실행해야하는데 이걸 트리 그림으로 봐보자
트리
리프노트 3 dfs(2)를 반환하고 dfs(1)에서 반복문이 종료되어 dfs(0) 으로 돌아가 다음 노드의 2를 실행하는 것이다.
이후 좀전에 1에서 했던 것처럼 dfs(1)의 반복을 n까지 하며 dfs(2)로 출력해내는 것을 m값인 3까지 반복한다.
이번 문제는 문제 풀이가 목적이 아닌 내용을 정리한 것이므로 정리 개념이 많다.
