[ 백준 15649 JAVA ] N과 M (1) (Feat. 백트래킹)

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

15649번: N과 M (1)

 

중복을 허용하지 않는 순열 

nPr

SOLVE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[] result;
	static boolean[] visit;
	
	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()); // 입력받기 완료 
		result = new int[M]; // 결과를 담을 배열  
		visit = new boolean[N];
		
		DFS(0);
	}// main end
	
	static void DFS(int depth) {
		if(depth==M) {
			for(int a : result) 
				System.out.print(a+" ");
			System.out.println();
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!visit[i]) { 
				visit[i] = true; // 해당 노드 방문 상태를 설정 
				result[depth] = i+1; // i+1값을 저장 
				DFS(depth+1); // 다음 자식 노드 방문을 위해 재귀 호출 
				visit[i]=false; // 자식 노드 방문 끝나고 방문노드를 방문하지 않은 상태로 돌려놓기. 
			}
		}
	}// method end
}

 

재귀 전체 구조 

 

입력이 4 2 인 경우 다음과 같은 재귀를 보인다. 

이해하려고 전부 그려보았다. 

반복문에서 i=0, i=1 일때 다음과 같다. 

 

반복문에서 i=2, i=3일때 다음과 같다. 

 

 

코드 참고자료

https://st-lab.tistory.com/114

---

백트래킹 개념 

여러가지 선택지들이 존재하는 상황에서 한가지를 선택한다.

선택이 이루어지면 새로운 선택지들의 집합이 생성된다.

이러한 선택을 반복하면서 최종 상태에 도달한다.

 

DFS vs 백트래킹 

깊이우선 탐색은 가능한 모든 경로를 탐색한다. 

백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지치기라고 한다. 불 필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 깊이우선탐색보다 더욱 효율적이다. 

 

백트래킹 기법 

어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다.

어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다. 

가지치기 : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.