[15650] N과 M (2)

다시 풀어보는 백트래킹 문제.

아직까지도 완벽히 숙지하지 못한 것 같다. (바로 N과 M 다른문제 풀러가야지)

우선 이 문제는 visited 배열이 필요가 없다. 왜냐하면 재귀적으로 호출할 때, +1을 해주면 앞에 적힌 수보다 자연스레 커지기 때문이다. 그래서 방문 확인용 배열이 필요가 없다! 중복 체크할 이유가 사라지기 때문이다.

나는 이거를 다른사람이 설명해줄 때에도 이해하는데 꽤나 어려움을 겪었다ㅠㅠ.. (그래도 확실히 해놔야 다른 백트래킹 문제를 풀어볼 수 있으리라 생각했기 때문이다.)

 

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
	static int n,m;
	static int[] arr;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		// 임시적으로 출력값을 저장할 배열
		arr = new int[m];
		dfs(1, 0);
		bw.flush();
	}
	
	public static void dfs(int a, int cnt) throws IOException {
    	// dfs 호출 순서를 보고싶다면
		System.out.println("a : " + a + " cnt : " + cnt);
    	// m개만큼 뽑았다면
		if(cnt == m) {
			for(int i=0; i<m; i++) {
				bw.write(arr[i] + " ");
			}
			bw.write("\n");
        // m개만큼 아직 못 뽑았다면
		} else {
			for(int i=a; i<=n; i++) {
				arr[cnt] = i;
				dfs(i + 1, cnt + 1);
			}
		}
		
	}
}

스스로도 이해하기 위해 손으로 dfs 호출을 그려보았다