[백준 15649 / N과 M(1) / JAVA / 완전 탐색]

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

문제 접근

입력한 N 숫자를 1부터 다 돌아가면서 중복없이 출력해야한다.

재귀 함수로 호출과 귀환을 반복하면서 모든 숫자를 탐색한다.

이해가 안되서 출력을 찍어가면서 했는데도 머리가 어지럽다.

이런 형태로 쓰인다라고 생각하고 필요하면 다시와서 봐야겠다.

import java.util.*;
import java.io.*;

public class Main {
	static int N; // 여러 메서드에서 공통 변수를 사용하기 위함
	static int M; 
	static boolean[] check;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
        check = new boolean[N+1];
        arr = new int[M+1];
       
        dfs(0); // 재귀 함수
	}
	
	static void dfs(int num) {
		// M이 4면 M이 3일 때 까지 재귀함수로 값들을 저장하고 해당 if문 실행
		if(num == M) {
			for(int i=0; i< M; i++) {
				System.out.print(arr[i]+ " ");
			}
			System.out.println("");
			return;
		}
		
		for(int i=1; i<= N; i++) {
			if(!check[i]) { // 중복 거르기? → num이 0일 때, arr[0]에 1 저장, check[1]은 true가 된다. num+1 시키고 이후 재귀함수 다시 호출, 그럼 check[1]은 true로 바뀌어있기 때문에
				// i=2로, check[2] = true로 arr[1] = 2로 된다. 이후 같은 패턴 반복
				
				check[i] = true;
				System.out.println("check["+ i +"]를 true로 바꿉니다.");
				
				arr[num] = i; // N만큼 돌면서 값을 arr배열에 저장, arr[0] = 1, arr[1] = 2, arr[2] = 3 ...
				System.out.println("arr["+ num +"]을 "+ i +"로 바꿉니다.");
				
				dfs(num+1); // 매개변수 1증가시키고 재귀 다시 호출
				
				check[i] = false; // 재귀로 dfs 끝까지 탐색한 뒤 다시 돌아오면서 false로 바꾸기
				System.out.println("check["+ i +"]를 false로 바꿉니다."); 
				
				// N, M / 4, 4의 경우
				// 재귀 끝내고 다시 돌아오면 i=3일 땐 i=4는 돌지않음, 3일 때 num은 2이며 arr[2] 자리엔 3이 있었는데 돌지않은 i=4를 돌면서, check[4]는 true로, arr[2] 자리엔 4가 들어간다
				// 그러면서 num이 2일 때 다시 재귀 호출 num은 3이 되면서 check[1,2,4]는 true로 되있기에 true인 check[3]일 때 arr[3]에 3이 들어간다. 1 2 3 4가 1 2 4 3으로 바뀌는 과정 
				// i=2일 땐 i=3,4는 돌리지않음
				// i=1일 때 i=2,3,4는 돌리지않았다
			}
		}
	}
}