[자료구조와 함께 배우는 알고리즘 입문] 5. 재귀 알고리즘 (2)

3. 하노이의 탑

 

이런 식으로 원반 위에 원반이 쌓여있는 탑을 맨 끝에 있는 기둥으로 옮기는 문제가 하노이의 탑이다.

맨위의 원반을 1, 가운데를 2, 마지막을 3이라고 가정하고 위의 과정을 조금 축소시켜서 말해보면

1) (1,2)를 Pole2로 옮긴다

2) (3)을 Pole3으로 옮긴다.

3) (1,2)를 Pole3으로 옮긴다.

고 생각할 수 있다.

원반이 몇 개가 쌓여있는 같은 과정으로 처리하면 된다.

이걸 재귀로 해결할 수 있는데, 코드로 표현해보면 아래와 같이 작성할 수 있다.

 

 

 static void move(int no, int x, int y){	
        //no = 원반 개수, x = 시작하는 기둥 번호, y = 맨 마지막 기둥 번호

        if(no>1){
            move(no-1,x,6-x-y);        		//no = 3, x = 1, y = 3이라고 하면
            								//모든 기둥 번호의 합은 6, 따라서 중간 기둥 번호는 6-x-y
        }
        System.out.printf("원반[%d]을 %d번 기둥에서 %d번 기둥으로 \n",no,x,y);
        if(no>1){
            move(no-1,6-x-y,y);
        }

    }

 

 

4. 8퀸 문제

8퀸 문제는 위의 그림처럼 8개의 퀸을 서로 공격해서 잡을 수 없도록 8*8 체스판에 두는 것이다.

(가능한 총 조합이 92가지나 된다고하는디,,,)

 

 

4-1. 퀸 배치하기

8*8 체스판이니까 총 64칸인 체스판에 처음 퀸 배치할 때는 아무데나 놔도 되지만, 다음 퀸을 배치할 때는 남은 63칸, 또 다음 퀸은 또 남은 칸...8번째 퀸의 자리를 선택할 때 까지 과정이 반복된다.

이렇게 되면 가능한 경우의 수가 무지막지하게 크고, 또 가능한 수 중 조건을 만족하는 경우를 걸러내기는 쉽지 않다.

 

때문에 몇 가지 규칙을 정해두고 문제를 해결해야 한다.

첫째로, 각 열에 퀸을 1개만 배치한다.

둘째로 각 행에 퀸을 1개만 배치한다.

 

그래도 아직 엄~~~~청 많은 경우의 수가 남아서 분기를 하면서 문제 해결을 해나가야 한다.

 

 

4-2. 분기 조작

분기를 하면서 퀸을 배치할 수 있는 모든 조합을 나열할건데, 분기 조작만으로는 8퀸을 해결할 수는 없다.

그래도 코드로 표현해보면 아래 같이 작성할 수 있다.

static int[]pos = new int[8];

    static void print(){
        for (int i = 0; i <pos.length ; i++) {
            System.out.print(pos[i]+" ");
        }
        System.out.println();
    }

    static void set(int i){
        for (int j = 0; j < 8; j++) {
            pos[i] = j;
            if(i==7){
                print();
            }else{
                set(i+1);
            }
        }
    }

 

 

 

4-3. 분기 한정법

 

두 번째 조건으로 설정해뒀던 조건을 고려하면서 이미 퀸이 배치된 행은 건너뛰고 나머지 행 내에서 퀸을 배치할 수 있도록 분기를 한정하는 코드이다.

필요하지 않은 분기를 없애 불필요한 조합을 줄여줄 수 있다.

물론 이것만으로도 8퀸 문제를 해결할 수는 없다.(왕 어렵)

 

static boolean[] flag = new boolean[8];
    static int[] pos = new int[8];
    
    static void print(){
        for (int i = 0; i < pos.length; i++) {
            System.out.print(pos[i]+" ");
        }
        System.out.println();
    }
    
    static void set(int i){
        for (int j = 0; j < 8; j++) {
            if(!flag[j]){
                pos[i]=j;
                if(i==7){
                    print();
                }
            }else{
                flag[j] = true;
                set(i+1);
                flag[j] = false;
            }
        }
    }

퀸이 어느 위치에 배치가 되면 flag의 해당 위치 부분을 true로 바꿔주고, 배치되지 않은 부분은 false로 저장해두어 저장된 위치에는 퀸이 배치되지 않도록 하는 것이다.

 

 

4-4. 8퀸 해결 프로그램

 

이제는 대각선 방향에서도 퀸이 1개만 배치될 수 있도록, 맨 첫 사진처럼 배치될 수 있도록 하는 코드를 작성해볼 것이다.

 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 < pos.length; i++) {
            System.out.print(pos[i]+" ");
        }
        System.out.println();
    }
    
    static void set(int i){
        for (int j = 0; j < 8; j++) {
            if(flag_a[j]==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);
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = false;
                }
            }
        }
    }

 

 

 

솔직히 어떻게 작동하는 건지는 아직 잘 이해안됨.... 

좀 더 공부하다보면 되지 않을까?????? 홧팅