[JAVA] 재귀 알고리즘(2)

자료구조와 함께 배우는 알고리즘 입문 - 자바

하노이의 탑

1. 바닥 원반을 제외한 그룹 (원반 [1] ~ 원반 [number-1])을 시작 기둥에서 중간 기둥으로 옮김
   -> move(number-1,x(시작 기둥),6-x-y(중간 기둥)
2. 바닥 원반 number를 시작 기둥에서 목표 기둥으로 옮겼음을 출력
3. 바닥 원반을 제외한 그룹 (원반 [1] ~ 원반 [number-1])을 중간 기둥에서 목표 기둥으로 옮김
   -> move(number-1,중간 기둥,목표 기둥)

책에 있는대로 따라가다가 모르겠어서 중간에 코드 한 번 바꿨음.

import java.util.Scanner;

public class Main {
//number = 원반의 개수 x=시작 기둥의 번호 y=목표 기둥 번호 
    public static void move(int number, int x, int y){
    
    //원반이 1개가 되면 그냥 출력 
        if(number == 1){
           System.out.println(x+" "+y+"\n");
           return;
       }
       // 이건 위랑 같음. 바닥 원반 빼고 시작 -> 중간
       move(number-1,x,6-x-y);
       System.out.println(x+" "+y+"\n");
       // 중간 -> 목표 
       move(number-1,6-x-y,y);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.print("원반 개수 : ");
        int n = sc.nextInt();

        move(n,1,3);
    }
}

8퀸 문제

예시 ) 서로 공격하여 잡을 수 없도록 8개의 퀸을 8*8 체스판에 놓으시오
행 방향, 열 방향, 대각선 방향으로도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정 조작이 필요함.

public class EightQueen {
    static boolean[] flag_a = new boolean[8]; //각 행에 퀸을 배치했는지
    static boolean[] flag_b = new boolean[15]; //대각선 방향으로 퀸을 배치했는지 /
    static boolean[] flag_c = new boolean[15]; //대각선 방향으로 퀸을 배치했는지 \
    static int[] pos = new int[8]; //각 열의 퀸의 위치

    static void print()
    {
        for(int i=0;i<8;i++){
            System.out.printf("%2d",pos[i]);
        }
        System.out.println();
    }
    static void set(int i){
        for(int j=0;j<8;j++){
            if(flag_a[i]==false && flag_b[i+j]==false && flag_c[i-j+7]==false){
                pos[i]=j;
                if(i==7){
                    print();
                }else{
                    flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=true;
                    set(i+1); // 재귀가 끝나면 퀸이 j행에서 제거되었기 때문에 false 처리
                    flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=false;
                }
            }
        }
    }
    public static void main(String[] args){
        set(0);
    }
}

백준 9663 N-Queen

참고 영상 : 파이썬으로 배우는 알고리즘 기초 : 19 n-Queens 문제의 구현

import java.util.*;

public class Main { 
    public static int N;
    public static int []map;
    public static StringBuilder sb = new StringBuilder();
    public static int queen_count = 0 ;

    public static void chess(int num){
        if(num==N){
            queen_count++;
            return;
        }

        for(int i=0;i<N;i++){
            map[num]=i;
            //놓을 수 있는 위치인가 아닌가
            if(promising(num)){
                chess(num+1);
            }
        }

    }

    public static boolean promising(int k){
        for(int i=0;i<k;i++){
        //i번째 행에서 퀸이 놓여있는 열
        //col번째 행에서 퀸이 놓여있는 열
        //같은 열에 놓이게 되므로, 유망 XX
            if(map[k]==map[i]){
                return false;
                //대각선 체크 -> arr[i]-arr[k] == i - k (절댓값) 
            }else if(Math.abs(i-k)==Math.abs(map[i]-map[k])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N=sc.nextInt();
        map = new int [N];

        chess(0);
        System.out.println(queen_count);
    }
}