알고리즘 - 백트래킹&순열

몇 개의 원소를 뽑을 지에 대해서 고정된 문제라면 for문을 여러번 써서 구현할 수 있으나, 매번 뽑아야 하는 원소의 수가 변경되는 경우라면 이 방법이 불가하다. 순열을 구현할 수 있는 다양한 방법을 고려해보자.

 

 

- swap 메서드를 활용한 순열 구현

import java.util.Arrays;

public class 순열_swap {
	static int[] nums; //배열
	static int N; 
	
	public static void main(String[] args) {
		nums = new int[] {1,2,3};
		N = nums.length;
		
		perm(0);
		
	}
	
	//idx : 현재 판단 하는 위치
	public static void perm(int idx) {
		//기저조건
        //N번째까지 판단을 다 마쳤다면 지금까지 뽑은 수를 출력하고 return;
		if(idx == N) {
			System.out.println(Arrays.toString(nums));
			return;
		}
		//재귀조건
        
       	//맨 앞자리부터 그 자리가 뒤의 모든 값의 숫자와 자리가 바뀌는 경우를 본다.
       
		for(int i = idx; i < N; i++) {
			swap(i, idx); 
			perm(idx+1); 
			swap(i, idx); //원상복구 하는 과정이 필요.
		}
		
	}
	
	//리턴값
//  [1, 2, 3] //perm(0) swap(0,0) perm(1)-> i=1; swap(1,1) ; perm(2) ->i=2; swap(2,2) 후 perm(3) return
// 	[1, 3, 2] //perm(0) swap(0,0) perm(1)-> i=2; swap(2,1) ; perm(2) -> i=2, swap(2,2) 후 perm(2) perm(1) return;
//	[2, 1, 3] //perm(1) swap(0,1) perm(1)-> i=1; swap(1,1) ; perm(2) -> i=2, swap(2,2) 후 perm(3) return;
//	[2, 3, 1] //perm(1) swap(0,1) perm(1)-> i=2; swap(1,2) ; perm(2) -> i=2, swap(2,2) 후 perm(3) return;
//	[3, 2, 1] //perm(2) swap(0,2) perm(1)-> i=1; swap(1,1) ; perm(2) -> i=2, swap(2,2) 후 perm(3) return;
//	[3, 1, 2] //perm(2) swap(0,2) perm(1)-> i=2; swap(1,2) ; perm(2) -> i=2, swap(2,2) 후 perm(3) return;
	
	
	//swap 메서드 
	//바꿀 인덱스 2개가 인자로 넘어와야한다. (배열을 static 하게 만들었으니까)
	//위의 경우가 아니라면 배열까지 인자로 같이 넘겨줘야한다.
	public static void swap(int a, int b) {
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;
	}
}

 

- 사용한 원소 체킹하는 재귀로 구현

import java.util.Arrays;

//visited
public class 순열_체킹 {
	static int[] nums;
	static int N;
	static boolean[] visited; //해당 원소 사용 유무
	static int[] result; //순열결과 저장
	
	public static void main(String[] args) {
		nums = new int[] {0,1,2};
		N = nums.length;
		result = new int[N];
		visited = new boolean[N];
		
		perm(0);
	}
	
	public static void perm(int idx) {
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		
		//모든 요소를 반복문을 통해 돌면서
		//사요하지 않은 원소가 있다면 결과에 넣고 사용했다고 표시도 하고 
		//다음 차례로 내려가 본다.
		for(int i = 0 ; i<N; i++) {
			//1. 원소를 사용했는지 체크하기
			if(visited[i]) continue;
			//요기에다가 작성 (실행된다는 것은 안 쓴 원소라는 뜻)
			result[idx] = nums[i];
			visited[i] = true; //해당 원소 사용했다고 체크하기
			perm(idx+1); //해당 원소 사용했을 때의 다음 원소 뽑기
            //위에서 호출한 함수가 끝나고 내려왔을 때니
            //이번 차례에서 위에서 체킹한 원소가 쓰일 때의 순열은 다 확인했다는 뜻.
            //=>체킹 해제
			visited[i] = false; 
		
		}