순열, 조합 연습

* DFS parameter에 대한 고찰 

void DFS(int level, int sum, int px, int py ... and so on);

1. level 

- 트리의 깊이를 나타냄

=> 문제 해결 시, 진행 횟수, 거리 등을 의미하며 최단 거리 구하기, 가장 횟수가 작은 경우의 수 찾기에 활용

=> 순열, 조합에서의 레벨은 N번째 순열 중, level 번째 인자를 의미.

2. sum

=> 단계별 누적합을 의미 순열 또는 조합과 결합하여 특정 경우의 수에 해당하는 합을 구할 때 사용.

3. px, py...

=> sum과 유사하지만 누적된 좌표 일 수도 있고, 현재 위치를 나타낼 수도 있음(미로 찾기)

4. 조합에서의 start

=> for문의 index와 결합하여, 조합을 완성, start부터 n까지의 경우만을 생성

     * 중복을 허용하지 않게 된다.

for (int i = start ; i <= n; i++) {
    combi[level] = i;
    DFS_COMBI(level+1, i+1 , combi);
}

ex) 1~3사이의 조합을 구하는 경우, 3C2

1 2 => lvl 0 ,start=1 index=1, lvl 1 ,start=2 index=2 

1 3 => lvl 0 ,start=1 index=1, lvl 1 ,start=2 index=3 

2 3 => lvl 0 ,start=1 index=2, lvl 1 ,start=3 index=3

 

 

 

import java.util.Scanner;


public class Main {
	
	static int n;
	static int m;
	static int []ch;
	static int []arr;
	
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
	
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		m = in.nextInt();
		Main M = new Main();
		// 4 2
		int combi [] = new int[m];
		int perm [] = new int[m];
		int ch [] = new int[n+1];
		//M.DFS_COMBI(0, 1,combi);
		M.DFS_PERM(0, perm, ch);
	
	}
	private void DFS_PERM(int level, int[] perm, int[] ch) {
		
		if (level == m) {
			for (int x : perm)
				System.out.print(x + " ");
			System.out.println();
		} else {
			for (int i = 1; i <= n ; i++) {
				if (ch[i] == 0) {
					ch[i] = 1;
					perm[level] = i;
					DFS_PERM(level + 1, perm, ch);
					ch[i] = 0;
				}
			}			
		}
		
		
	}
	public void DFS_COMBI(int level, int start, int[]combi ) {
		
		if(level == m) {
			//System.out.println("lvl : "+level);
			for (int x : combi)
				System.out.print(x+ " ");
			System.out.println();
		} else {
			
			for (int i = start ; i <= n; i++) {
				combi[level] = i;
				DFS_COMBI(level+1, i+1 , combi);
			}
			
		}
		
	}

	
}