[Algorithm] 재귀함수에 대해

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 재귀함수에 대해 전체적인 정의와 개념들에 대해서 정리해볼까 합니다.

따라서 비정기적으로 업데이트됩니다. ㅎㅎ

 

 

 

재귀함수의 정의

함수 내에서 자기 자신을 호출하는 함수.

 

 

 

재귀함수의 조건

1. 반드시 재귀호출을 하지 않는 base case가 존재해야 한다.
2. 모든 case는 base case로 수렴해야 한다.

 

 

 

설계 원칙

암시적 변수를 명시적 매개변수로 바꾼다

int sequentialSearch(int[] arr, int index, int target) {
    for(int i=0; i < index; i++) {
        if(arr[i] == target) return i;
    }
    return -1;
}

만약 위와 같이 순차탐색을 하는 함수가 있는 경우, 시작 인덱스를 암시적으로 0으로 가정한 코드입니다.

이런 암시적 변수를 명시적 매개변수로 변환하여, 몇번째 인덱스부터 몇번째 인덱스까지 탐색할 것인지 정의하는 것이 좋습니다. (혹은 시작 인덱스와 검사할 요소 개수를 인자로 받도록 하는 것도 가능합니다.)

 

해당 설계 원칙을 적용한 재귀적 순차탐색 함수는 다음과 같습니다.

int sequentialSearch(int[] arr, int start, int end, int target) {
    if(start > end) return -1;
    else if (arr[start] == target) return start;
    else return sequentialSearch(arr, start+1, end, target);
}

 

 

 

응용

미로 찾기

현재 위치에서 출구까지 경로가 존재하는 조건은 다음과 같습니다.

1. 현재 위치가 출구이거나 (base case)
2. 인접한 셀에 대해, 현재 셀을 지나지 않고 출구까지의 경로가 존재 

 

boolean findPath(x, y) {
    if (x, y) is the exit
    	return true;
    else
    	mark (x, y) as a visited cell;
    	for ((a, b) : neighbour cells) {
            // if neighbour cell is not wall and not visited
            if (a, b) is on pathway && (a, b) is not visited
            	if findPaht(a, b)
                	return true;
        }
        return false;
}

간단한 슈도코드입니다.

 

 

연결된 픽셀 수 찾기

1과 0의 값을 가지는 픽셀들로 이루어진 NxN 이미지가 있다고 가정합니다.

1의 값을 가지는 픽셀에 대해, 인접한 8개의 픽셀중에 같은 1의 값을 가진 픽셀이 존재할 경우, 두 픽셀은 연결되어 있다고 하며, 연결된 픽셀들의 집합을 블롭(blob)이라고 합니다. (즉, 상하좌우 대각선 방향으로 연결이 가능합니다.)

이 때, 이미지 파일에서 특정 픽셀을 골랐을 때, 해당 픽셀이 포함된 블롭의 총 픽셀 수를 세는 문제입니다. (즉, 연결된 픽셀 수를 세는 문제라고 할 수 있습니다.)

 

int countBlob(int x, int y) {
    int counter = 0;
    if pixel(x, y) is out of boundary {
        return counter;
    }
    else if pixel(x, y) is not image pixel or pixel(x, y) is already counted image pixel {
    	return counter;
    }
    else {
        set pixel(x, y) to be counted
        return counter + countBlob(x-1, y) + countBlob(x-1, y+1) + countBlob(x, y+1) +
            countBlob(x+1, y+1) + countBlob(x+1, y) + countBlob(x+1, y-1) +
            countBlob(x, y-1) + countBlob(x-1, y-1);
    }
}

위는 간단한 슈도코드입니다.

탐색 순서는 북쪽에서 시작하여 시계방향으로 진행합니다.

 

private int BACKGROUND_PIXEL = 0;
private int IMAGE_PIXEL = 1;
private int COUNTED_PIXEL = 2;

int countBlob(int x, int y) {
    int counter = 0;
    if (x < 0 || x >= N || y < 0 || y >= N) {
        return counter;
    }
    else if (pixel[x][y] != IMAGE_PIXEL) {
    	return counter;
    }
    else {
        pixel[x][y] = COUNTED_PIXEL;
        counter++;
        return counter + countBlob(x-1, y) + countBlob(x-1, y+1) + countBlob(x, y+1) +
            countBlob(x+1, y+1) + countBlob(x+1, y) + countBlob(x+1, y-1) +
            countBlob(x, y-1) + countBlob(x-1, y-1);
    }
}

자세한 자바 코드입니다.

 

 

N queen problem

8 queen problem

NxN의 체스판에서, N개의 퀸이 서로를 잡아먹지 않도록 배치하는 문제입니다.

퀸은 상하좌우 대각선방향으로 칸수 제한없이 이동할 수 있으므로, 잘 배치해야 합니다.

 

백트래킹(backtracking)

기본적인 해결 방법은, 백트랙킹을 이용하는 것입니다.

즉, (0,0)에 퀸을 배치하고, (1,1)에 퀸을 배치하고... 이와 같은 방식으로 N개의 퀸을 배치합니다.

만약 목표를 달성할 수 없다면, 이전 상태로 되돌아가서 다른 선택을 시도하는 것입니다.

백트래킹은 아래에 나와 있는 상태공간 트리를 깊이 우선 탐색(depth first search)을 하는 기법입니다.

 

상태공간 트리(state space tree)

state space tree

위와 같은 백트래킹을 이용하기 위해, 모든 상태를 가시적인 형태로 표현한 것이 상태공간 트리입니다.

해당 트리를 체계적으로 탐색한다면, 반드시 해를 찾을 수 있습니다.

조건을 만족하지 못하여, 더이상 탐색할 필요가 없는 노드를 'non-promising'노드라고 합니다.

 

솔루션

그렇다면 백트래킹을 이용한 N queen problem은 어떻게 코드로 구현해야 할까요?

대표적인 방법으로 재귀를 이용한 방법과 스택을 이용한 방법이 있습니다.

이 포스트에서는 재귀에 대해 설명하므로, 재귀를 이용한 방법을 소개해 드리겠습니다.

 

import java.util.Scanner;

public class Q9663_nQueen {
    private int N;
    private int[] cols;

    public void main() {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        cols = new int[N + 1];

        queen(0);
    }

    // 임의의 열에 퀸을 배치한 row에 대해, promising한지 검사합니다
    private void queen(int row) {
        // 배치된 퀸이 다른 퀸과 충돌하는 경우
        if (!promising(row)) return;

        // 다른 퀸과 충돌하지 않으면서, 마지막 행에 퀸을 배치한 경우
        if (row == N) {
            // 해당 노드가 해에 해당하는 경우, 각 퀸의 위치를 출력합니다.
            for (int i = 1; i <= N; i++) {
                System.out.println(String.format("[%d, %d]", i, cols[i]));
            }
        } else {
            for (int i = 1; i <= N; i++) {
                // 현재 행까지는 배치가 완료되었으며, 다음 행에 임의로 배치 후 promising한지 검사합니다
                cols[row + 1] = i;
                queen(row + 1);
            }
        }
    }

    // 해당 함수가 호출된 row에 대해, row-1번째 퀸까지는 정상적으로 배치되었음을 전제로 합니다.
    // 즉, row번째 퀸과 그 이전의 퀸들과 충돌 여부만 검사하면 됩니다.
    private boolean promising(int row) {
        // 0번째 행에는 퀸을 배치하지 않으므로, true를 반환합니다
        if (row == 0) return true;

        for (int i = 1; i < row; i++) {
            // 같은 열에 다른 퀸이 존재하는지 검사합니다.
            if (cols[row] == cols[i]) return false;
            // 대각선에 다른 퀸이 존재하는지 검사합니다.
            else if (row - i == Math.abs(cols[row] - cols[i])) return false;
        }
        return true;
    }
}

여기서 깊이(depth)가 0인 노드는, 어떠한 queen도 배치하지 않았음을 의미합니다.

체스판을 표현하기 위해 기본적으로 NxN의 이차원 배열이 필요하지만, N queen problem에서는 한 행에는 하나의 퀸 밖에 존재할 수 없으므로, 각 열에 몇번째 퀸(몇번째 행의 퀸)이 존재하는지 표현하면 충분합니다. 즉, 위 그림의 예시대로라면 cols = [0, 3, 1, 4, 2]가 됩니다.

다음과 같은 이유로, 함수의 인자로는 행번호와 열번호 대신 깊이를 받습니다.

• queen함수가 호출되었다는 것은 그 이전 행들의 퀸들은 배치가 완료되었음을 의미합니다.
• 상태공간 트리에서 깊이는 몇번째 퀸(몇번째 행)인지 의미합니다.

우선 promising한지는 promising이라는 함수를 통해 판정하도록 합니다. 해당 노드가 promising하지 않다면 더이상 탐색을 진행하지 않고 false를 반환합니다.

promising하면서 깊이가 N이라면 모든 퀸을 배치했다는 말이므로, 해당 노드는 해에 해당합니다. 모든 퀸의 위치를 출력한 후, true를 반환합니다.

promising한데 깊이가 N이 아니라면 아직 모든 퀸을 배치하지 못했다는 말이므로, 자식 노드를 더 탐색합니다. 다음 퀸을 1열부터 N열까지 배치했다고 가정을 한 뒤, 다음 깊이를 판단하기 위해 queen(depth + 1)을 호출합니다. 만약 해당 가정이 해에 해당해서 true를 반환한다면 더 이상의 탐색을 방지하기 위해 true를 반환합니다.

모든 자식노드가 promising하지 않다면, 백트래킹을 위해 false를 반환합니다.

 

 

 

멱집합(power set)

멱집합은 모든 부분집합의 집합입니다.

 

멱집합을 구하는 방법

집합 S={a, b, ..., n}이 주어졌을 때, 재귀를 이용하여 S의 멱집합을 구하는 방법은 다음과 같습니다.

1. a를 포함하지 않는 부분집합을 구한다. 즉, a를 제외한 집합 S'={b, ..., n}의 모든 부분집합을 구한다.
2. a를 포함하는 부분집합을 구한다. 즉, S'의 모든 부분집합에 a를 추가한다.
3. 1과 2에서 구한 집합을 하나의 집합으로 묶어준다.

 

상태공간 트리

집합 S={a, b, c}의 상태공간 트리

집합 S={a, b, c}의 상태공간 트리는 위와 같습니다.

여기서 k는 S에서의 인덱스라고 생각하시면 됩니다.

k=1에서는 S의 첫번째 요소인 a의 포함여부에 따라 자식 노드가 갈립니다.

a를 포함하지 않는 경우, 나머지 집합은 S'={b, c}가 되며, 여기서 또 b의 포함 여부를 결정합니다.

이런식으로 모든 요소에 대해 포함 여부를 결정한다면, 모든 잎 노드는 멱집합의 요소가 됩니다.

 

솔루션

private char[] set = {'a', 'b', 'c'};
private int N = set.length;
private boolean[] include = new boolean[N];

private void powerSet(int k){
    if(k==N) {
        System.out.print("{");
        for(int i=0; i<N; i++){
            if(include[i]) System.out.print(set[i] + " ");
        }
        System.out.println("}");
    }
    else {
        // exclude
        include[k] = false;
        powerSet(k+1);

        // include
        include[k] = true;
        powerSet(k+1);
    }
}

자세한 자바 알고리즘은 위와 같습니다.

 

 

참고

인프런 - 영리한 프로그래밍을 위한 알고리즘 강좌

https://codepumpkin.com/n-queen-problem/

N Queen Problem Using Recursive Backtracking | Code Pumpkin

https://www.javatpoint.com/n-queens-problems

N Queens Problems - javatpoint