상세 컨텐츠

본문 제목

재귀 알고리즘 예제(하노이의 탑, 8퀸 문제)

자료구조와 알고리즘/자료구조, 알고리즘

by Banjosh 2023. 1. 13. 09:29

본문

  • 하노이의 탑

    1. 하노이의 탑 문제 알아보기

 하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수는 없다.

 

    2. 문제 푸는 알고리즘 짜기

 우선 2개의 원반을 옮긴다고 생각해보자. 맨 위의 원반을 중간 기둥에 옮기고, 맨 아래 원반을 목표 기둥에 옮기고, 중간 기둥에 옮겨놨던 맨 위의 원반을 목표 기둥에 옮기면 완성된다(기둥 3개를 시작 기둥, 중간 기둥, 목표 기둥으로 부르자).

 이번엔 3개의 원반을 옮긴다고 생각해보자. 맨 위와 두번째 원반을 2개의 원반을 옮기는 법으로 중간 기둥으로 옮기고, 마지막 원반을 목표 기둥에 옮기고, 다시 중간 기둥에 옮겨놨던 2개의 원반을 다시 2개의 원반을 옮기는 법으로 목표 기둥에 옮겨놓는다.

 자 혹시 규칙이 보이는가? n개의 원반을 옮기는 방법은 맨 위의 원반부터 마지막 전까지의 n-1개 원반을 중간 기둥에 옮기고, 마지막 원반을 목표 기둥에 옮기고, n-1개의 원반을 다시 목표 기둥에 옮긴다. 여기서 필요한 n-1개의 원반을 옮기는 방법은 다시 n-1개의 원반을 옮기는 방법을 찾는 재귀 호출을 이용한다.

 

    3. 코드 작성하기

import java.util.Scanner;
public class Main {
    static void move(int no, int x, int y){
        if(no>1){
            move(no-1,x,6-x-y); 
            // n-1개의 원반을 중간 기둥에 옮김
        }
        System.out.printf("원반[%d]을(를) %d번 기둥에서 %d번 기둥으로 옮김\n",no,x,y);
            // 맨 마지막 원반을 목표 기둥에 옮김
        if(no>1){
            move(no-1,6-x-y,y);
            // n-1개의 원반을 목표 기둥에 옮김
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int no = sc.nextInt();
        move(no,1,3);
    }
}

  다음과 같이 move메서드를 재귀 호출을 2번하는 메소드로 만든다. 그리고 알고리즘 짤때 생각했던 3단계를 실행하는 메서드로 만드는데 1단계는 n-1개의 원반을 중간 기둥에 옮기고, 2단계는 맨 마지막이었던 원반을 목표 기둥에 옮기고, 3단계는 n-1개의 원반을 목표 기둥에 옮기는 코드를 작성한다. 여기서 중간에 6-x-y가 보이는데 이는 현재 중간 기둥을 의미한다. 재귀를 구현할 때는 생각을 깊게하는게 오히려 독이 된다. 따라서 분석하기보단 내가 짠 알고리즘을 믿고 그대로 옮겨 적는 것이 중요하다.

 

  • 8퀸 문제

    1. 8퀸 문제 알아보기

8퀸 문제는 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장할 뿐만 아니라 19세기의 유명한 수학자 가우스가 잘못된 해답을 내놓은 것으로도 잘 알려져있다. '서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓으시오'가 문제이다. 퀸은 가로, 세로, 대각선으로 마음대로 움직일 수 있으므로 이를 잘 생각하여 문제를 풀어야 한다.

 

    2. 8퀸 문제 풀기

 이 문제의 본질을 퀸 8개를 배치하는 것이다. 그러면 아무런 조건없이 퀸을 배치하는 방법을 생각해보자. 체스판이 0~7행, 0~7열로 이루어져 있으므로 전체 배치 방법을 N이라 하면 N = 64 x 63 x 62 x 61 x 60 x 59 x 58 x 57 이 된다. 이제 부터 여기에 조건을 1개씩 추가해 경우의 수를 줄여가보자. 우선 조건을 크게 3가지로 나누어 보자.

 

      조건 1. 퀸은 세로로 어디든 움직일 수 있다. (같은 열에 퀸의 배치가 겹치면 안된다.)

      조건 2. 퀸은 가로로 어디든 움직일 수 있다. (같은 행에 퀸의 배치가 겹치면 안된다.)

      조건 3. 퀸은 대각선으로 어디든 움직일 수 있다. (같은 대각선 위에 퀸의 배치가 겹치면 안된다.)

 

    1) 분기 조작 (가지 뻗기)

 분기 조작이란 가지가 뻗어 나가듯이 문제를 나누어 푸는 과정을 말한다. 우리는 조건 1을 만족시키기 위해 모든 경우의 수를 분기하여 찾는 방법을 사용할 것이다. 조건 1을 분석해 보면 같은 열에 퀸들의 배치가 겹치면 안되므로 모든 열은 1개의 열에 1개의 퀸만 존재할 수 있다. 이러한 조건 속에서 0열부터 7열까지 차례로 퀸을 배치하며 경우의 수를 찾아보자. 먼저 0열에 퀸을 배치하는 방법은 0행 ~ 7행까지 8가지가 있다. 그 다음인 1열에 퀸을 배치하는 경우도 0행 ~ 7행까지 8가지가 있다. 하지만 우리는 가지가 뻗어 나가듯이 경우의 수를 구하고 있으므로 0열의 0행에 퀸이 있는 경우 + 1열에 0행~7행에 퀸이 있는 경우 8가지, 0열의 1행에 퀸이 있는 경우 + 1열에 0행~7행에 퀸이 있는 경우 8가지 이런식으로 0열의 경우의 수 8가지마다 1열의 경우의 수 8가지가 가지처럼 뻗어나가 총 64개의 경우의 수가 된다. 따라서 이런식으로 N을 구해보면, N = 8 x 8 x 8 x 8 x 8 x 8 x 8 x 8 가 되고 무작정 구했던 N에 비해 크게 줄었다. 분기 조작방법을 이용한 경우의 수 찾기를 코드로 확인해보자.

public class Main {
    static int[] pos = new int[8];
    static void print(){
        for(int i=0; i<8;i++){
            System.out.print(pos[i]+" ");
        }
        System.out.println();
    }
    static void set(int j){
        for(int i = 0; i<8; i++){
           pos[j]=i; // j열의 i행에 퀸 배치
            if(j==7){ // 7열까지 배치가 끝나면 출력
                print();
            }else set(j+1); //아니면 j+1열에 퀸 배치
        }
    }
    public static void main(String[] args){
        set(0);
    }
}

 set(0)을 통해 0열부터 분기 조작을 시작한다. pos[j] = i 는 i행 j열에 퀸이 배치된 것을 나타내고 set 메서드 반복문 안에서 j가 7인 경우까지 pos 입력이 끝났으면 print메서드로 넘어가 배치가 끝난 퀸의 위치를 출력한다. 출력이 끝나면 그 다음 배치를 찾아 또 출력하고 이를 0 0 0 0 0 0 0 0 에서  7 7 7 7 7 7 7 7 까지 반복한다.

 

    2) 분기 한정법

  규칙 2, 3은 Integer 배열 pos를 이용했던 분기 조작과 달리 boolean 배열을 이용한 분기 한정법을 이용할 것이다. 분기 한정법이란 분기 조작 중에 필요없는 분기는 제거하여 굳이 실행하지 않 는 방법이다. 그러면 분기 한정법을 통해 조건 2를 만족시켜 보자. 규칙 2는 같은 행에 퀸의 배치가 겹치면 안된다는 내용이다. boolean 배열의 n번째 요소는 n번째 행의 배치 여부를 나타내고 n번째 행에 퀸이 배치되어 있다면 true, 아니면 false가 입력되어 있다. 따라서 n번째 행에 퀸을 배치하고 싶을 때는 항상 배열의 요솟값이 true인지 false인지 확인해야 한다. 

public class Main {
    static int[] pos = new int[8];
    static boolean[] Hg = new boolean[8];
    static void print(){
        for(int i=0; i<8;i++){
            System.out.print(pos[i]+" ");
        }
        System.out.println();
    }
    static void set(int j){
        for(int i = 0; i<8; i++) {
            if (!Hg[i]) {
                pos[j] = i; // j열의 i행에 퀸 배치
                if (j == 7) { // 7열까지 배치가 끝나면 출력
                    print();
                } else{
                    Hg[i] = true;
                    set(j + 1);
                    Hg[i] = false;
                }
            }
        }
    }
    public static void main(String[] args){
        set(0);
    }
}

 조건 1을 만족하는 코드에 조건 2를 만족하는 내용을 추가해 보았다. 배열 Hg는 i행에 퀸이 배치됐는지 안됐는지 알려준다. 따라서 set 메서드 for문의 맨 처음 조건식으로 i행에 퀸이 배치되어 있으면 그냥 아무것도 안하고 넘어가게 만들었다. 반대로 i행에 퀸이 없어 배치가 가능하면 i행 j열에 퀸을 배치하고, 7열까지 배치가 안끝난 경우 Hg[i] = true를 실행해 i행에 퀸이 배치되었다는 것을 표시한 후 set(j+i)로 다음 열 배치로 넘어간다. set(j +1) 밑에 Hg[i] = false가 있는데 이는 set(j + 1)이 다 진행되고 나왔을때 for문에 의해 다음 i값으로 넘어가야 하므로 Hg[i] 값을 원래대로 false로 해놓는 것이다. 이렇게 조건 2까지 만족하면 N = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 8!이 된다.

 

 마지막으로 분기 한정법을 이용하여 조건 3까지 만족해 보자. 대각선을 한정하기 위해서는 왼쪽위에서 오른쪽 아래로 내려가는 대각선 1개 ( \ ), 오른쪽 위에서 왼쪽 아래로 내려가는 대각선 1개 ( / ) 이렇게 2개를 체크하는 boolean 배열이 1개씩 2개 필요하다. 문제 푸는 방법은 조건 2 때와 크게 다르지 않으므로 코드를 작성해 보자.

public class Main {
    static int[] pos = new int[8];
    static boolean[] Hg = new boolean[8];
    static boolean[] Check1 = new boolean[15];
    static boolean[] Check2 = new boolean[15];
    static void print(){
        for(int i=0; i<8;i++){
            System.out.print(pos[i]+" ");
        }
        System.out.println();
    }
    static void set(int j){
        for(int i = 0; i<8; i++) {
            if (!Hg[i]&&!Check1[i+j]&&!Check2[7-i+j]) {
                pos[j] = i; // j열의 i행에 퀸 배치
                if (j == 7) { // 7열까지 배치가 끝나면 출력
                    print();
                } else{
                    Hg[i] = Check1[i+j] = Check2[7-i+j] = true;
                    set(j + 1);
                    Hg[i] = Check1[i+j] = Check2[7-i+j] = false;
                }
            }
        }
    }
    public static void main(String[] args){
        set(0);
    }
}

 조건 3을 구현한 위 코드를 이해하려면 Check1과 Check2 boolean 배열을 이해하면 된다. Check1이 / 대각선이고 Check2가 \ 대각선이다. Check1, Check2 배열은 15개의 대각선을 검사하기 위해 0~14 index에 true, false가 입력되어있다. 각각의 대각선을 index로 표시해 보면 다음과 같다.

 

                                                                Check 1 (/)

0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14

 

                                                                 Check 2 (\)

7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7

 

 i 행 j 열의 대각선 위치는 Check1의 경우 index = i+j 이고 Check2의 경우 index = 7-i+j 이다. index만 신경써서 아까 Hg배열 처럼 넣어주면 한정 조건이 2개 더 생기게 되고 이것이 대각선마다 퀸이 1개씩만 배치될 조건을 만족시켜 결국 조건 1, 2, 3을 전부 만족시키게 된다. 결국 최종 N = 92개로 8퀸 문제가 해결된다

 

 

'자료구조와 알고리즘 > 자료구조, 알고리즘' 카테고리의 다른 글

정렬 알고리즘 2 (셸 정렬, 퀵 정렬)  (0) 2023.01.18
정렬 알고리즘 1 (단순 정렬)  (0) 2023.01.17
재귀 알고리즘  (0) 2023.01.13
링 버퍼  (1) 2023.01.11
스택(Stack)과 큐(Queue) 그리고 덱(Deque)  (0) 2023.01.10

관련글 더보기

티스토리툴바