[JAVA]再帰アルゴリズム(2)

資料構造とともに学習するアルゴリズム入門-Java

ハノイの塔

底部円盤以外のグループ(円盤[1]~円盤[number-1])を始柱から中間柱に移動
->move(番号-1,x(始発柱)、6-x-y(中間柱)

底部円盤数が始点柱から目標柱に移動する

を出力する.

底部円盤以外のグループ(円盤[1]~円盤[number-1])を中間柱から目標柱へ移動
->move(番号-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

参照ビデオ:Python学習アルゴリズム基礎: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);
    }
}