(자료구조 & 알고리즘 정리) 완전 탐색, 백트래킹 (2023.06.14)

1. 순열 구현

---

1) 비트마스킹

input[]
numbers[] 

perm(cnt, flag) {

	if cnt == N 
    	return;
        
    for (i from 0 to N-1){
    	if (flag & 1<<i) != 0 then continue
        numbers[cnt] = input[i]
        perm(cnt +1, flag | 1<<i)
    }
    
 }

 

 

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

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; 
		
		}

 

3) 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;
	}
}

 

 

2. 백트래킹

---

1) 완전탐색 + 가지치기

• 모든 조합을 시도해서 문제의 해를 찾음
• 해를 얻을 때까지 모든 가능성 시도
• 모든 가능성은 하나의 트리처럼 구성
• 여러 선택지들이 존재하는 상황에서 하나의 가지를 선택
• 선택이 이루어지면 새로운 선택지들의 집합 생성
• 위 과정을 반복하며 최종 상태에 도달
• 보통 재귀로 구현

2) 상태공간 트리를 깊이를 따라 가는 방식이므로 DFS 

- 어떤 노드의 해 가능성을 점검 후 해가 아니라고 판단되면 그 노드의 부모로 되돌아간 후 다음 자식 노드로 가기

- 해의 가능성이 없는 노드가 포함되는 경로는 더 이상 고려 X

 

 

 

 

 

 

3. 문제

---

1) 완전탐색

 

 

2) 백트래킹

-NQueen