[알고리즘 기법] 분기한정법 ( Branch and Bound )

728x90

 

◇  설명

  -  백트래킹을 개선
  -  가지뻗기 + 한정 조작( bounding )
   ※  한정 조작  :  필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법

 

◇  코드

  ex)  N-Queens

 Q)  크기가 N*N인 체스판에 N개의 퀸 말을 같은 행, 대각선1, 2 와 겹치지 않게 배치할 수 있는 경우의 수,
      각 열에 배치된 말의 행 출력

import java.util.Arrays;
import java.util.Scanner;

public class Main {  // 백준 9663번

	static boolean[] flag_a, flag_b, flag_c;
	static int n, cnt = 0, pos[];
	
	static void set( int i ) {
		for( int j = 0; j < n; j++ ) {
			if( flag_a[j] == false && flag_b[i+j] == false && flag_c[i-j+(n-1)] == false ) {
				pos[i] = j;
				if( i == (n-1) ) {
					System.out.println( Arrays.toString( pos ) );  
					cnt++;
				}
				else {
					flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = true;
					set( i + 1 );
					flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) {

		// 크기가 N*N인 체스판에 N개의 퀸 말을 같은 행, 대각선1, 2 와 
		// 겹치지 않게 배치할 수 있는 경우의 수, 각 열에 배치된 말의 행 출력
		
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.close();

		flag_a = new boolean[n];
		flag_b = new boolean[2*n-1];
		flag_c = new boolean[2*n-1];
		pos = new int[n];
		
		set(0);

		System.out.println(cnt);
	}
}

( https://hyunjiishailey.tistory.com/175 )

 

◇  출처  :  Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바 

 

 

반응형