[Algorithm /백준] N과 M (1)

[문제]
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

[입력]
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

[출력]
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

[예제 입력1]

3 1

[예제 출력1]

1
2
3

 

 

[예제 입력2]

4 2

[예제 출력2]

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

 

[문제 해결]

import java.util.Scanner;

public class Main {
	/*
	 *N과 M 출력 예시
	  (4,2)
	  [출력]  
	    1 2                   
	    1 3
	    1 4
	    2 1
	    2 3
	    2 4
	    3 1
	    3 2
	    3 4 
	    4 1
	    4 2
	    4 3 
	   => M만큼 가로로 출력
	      N만큼 세로로 출력
	      M == N인 경우는 넣지 않음. 
	 */
	private static boolean[] visit;
	private static int[] arr;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		visit = new boolean[n]; //n은 세로로 출력되는 요소 체크해줌.
		arr = new int[m]; //m은 가로로 출력되는 요소를 담아둠.
		
		for(int i = 0; i <visit.length;i++) {
			visit[i] = false;
		}
		
		Main nm = new Main();
		
		nm.printNanM(n,m,0);
	}
	
	public void printNanM(int n, int m, int depth) {
		
		if(depth == m) {
			for(int i = 0 ; i < m; i++) {
			 System.out.print(arr[i]+ " ");
			}
			System.out.println();
			return;
		}
		else {
			for(int i=0 ; i < n; i++) { //세로로 출력되는 요소
				 if(!visit[i]) {
					 arr[depth]= i+1; //가로로 출력되는 요소
					 visit[i] = true;
					 printNanM(n, m , depth+1);
					 visit[i] = false;
				 }
			}
		}
	}
}

 

 

+) 개인적으로 이해하기 너무너무 어려웠던 문제... 백트래킹 너무어렵다......................