3. 다중 순환

5. 다중 순환

- 다중 순환이란

• 순환 함수들은 호출이 발생할 때마다 몇 개의 순환 호출이 이루어지는가에 따라 선형 순환, 이진 순환 그리고 다중 순환으로 나눌 수 있음

1. 선형 순환(linear recursion): 함수의 호출이 발생하면 최대로 하나의 순환 호출이 이루어지는 경우를 말함(팩토리얼, 거듭제곱)
2. 이진 순환(binary recursion): 함수에서 두 개의 순환 호출이 발생하는 경우(피보나치 수열, 하오니 탑)
3. 다중 순환(multiple recursion): 하나의 함수에서 두 개 이상의 순환 호출이 이루어지는 경우

- 영역 채색 문제

영역 채색(blob coloring), 연결 화소 분석법(connected component labeling): g흑과 백의 화소 값만을 갖는 이진 영상(binary image)에서 연결된 객체를 찾는 방법

• 이진 영상을 스캔하다가 흰 화소를 만나면 어떤 색으로 칠함.
• 그리고 이 화소와 인접한 네 방향의 이웃 화소에 대해 순환적으로 검사하면서 같은 색을 칠함 -> 즉, 4 방향으로 순환 호출을 하는 다중 호출 사례

<프로그램 2.5.1> 영역 채색 문제 프로그램

#include <cstdio>
#define WIDTH 20
#define HEIGHT 9

using namespace std;

// 순환 호출 함수 (다중 순환의 예)
void labelComponent(unsigned char img[HEIGHT][WIDTH], int x, int y, int label)
{
    if (x < 0 || y < 0 || x >= WIDTH || y >= HEIGHT) // 영상의 밖이면 return
        return;
    if (img[y][x] == 9) { // 처리 안된 전경 화소이면
        img[y][x] = label; // label로 화소 값을 바꾸고
        labelComponent(img, x - 1, y, label); // 순환 호출: 좌측 이웃화소
        labelComponent(img, x, y - 1, label); // 순환 호출: 상측 이웃화소
        labelComponent(img, x + 1, y, label); // 순환 호출: 우측 이웃화소
        labelComponent(img, x, y + 1, label); // 순환 호출: 하측 이웃화소
    }
}

// 이진 영상의 영역 채색(blob coloring) 함수
void blobColoring(unsigned char img[HEIGHT][WIDTH])
{
    int label = 1; // label은 1부터 시작함
    for (int y = 0; y < HEIGHT; y++) { // 영상의 모든 화소에 대해
        for (int x = 0; x < WIDTH; x++) {
            if (img[y][x] == 9) // 처리가 안된 전경 화소이면
                labelComponent(img, x, y, label++); // 연결화소 채색 시작
        }
    }
}

// 영상의 화소 값을 화면에 출력하는 함수
void printImage(unsigned char img[HEIGHT][WIDTH], char* msg)
{
    printf("%s\n", msg);
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            if (img[y][x] == 0) {
                printf(".");
            } else {
                printf("%-1d", img[y][x]);
            }
        }
        printf("\n");
    }
    printf("\n");
}

// 주 함수
int main()
{
    // 입력 영상 : 자료 !
    unsigned char img[HEIGHT][WIDTH] = {
        0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 9, 9,
        9, 9, 9, 9, 9, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 9, 9,
        0, 0, 9, 0, 0, 0, 9, 0, 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 9, 9,
        0, 9, 9, 9, 0, 0, 9, 9, 9, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9, 9,
        0, 9, 0, 9, 0, 0, 9, 0, 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 9, 9,
        9, 9, 0, 9, 9, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9,
        9, 0, 0, 0, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 0, 0, 0, 0, 0,
        9, 0, 0, 0, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 0, 0, 0, 9, 9,
        0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 9, 9
    };

    printImage(img, (char*)"<Original image>");
    blobColoring(img);
    printImage(img, (char*)"<Labelled image>");
    return 0;
}

-> 입력 영상의 "자료!"란 글자의 각 연결된 부분들 (ㅈ, ㅏ, ㄹ, ㅛ, 느낌표(!)의 두 영역)이 각각의 객체가 되어 채색되었으며 전체 6개의 객체가 검출된 것을 알 수 있음.
-> 이 프로그램은 실제로 객체 영역의 크기가 크지 않은 경우 매우 안정적으로 실행됨
-> 영상의 크기가 크고, 객체 영역의 면적이 매우 넓은 경우 실행속도가 느려지며 심한 경우 스택 오버플로우가 발생할 수 있음.
-> 따라서, 일반적으로는 주사선 알고리즘(scanline algorithm)을 사용함, 반복문을 사용해서 코드가 매우 복잡하지만 처리시간이 빠르고, 영상의 크기와 상관없이 일정한 시간 안에 결과를 얻을 수 있음.

- 미로 탐색 문제

• 미로 찾기 문제도 순환을 이용하여 구현할 수 있음
• 어떤 위치에서 이웃하는 4 방향에 대해 순환 호출이 이루어지는 지 유의, 현재 위치가 출구의 위치와 동일하면 탐색 성공이며, 탐색이 성공하면 더 이상 순환 호출을 하지 않도록 done 변수를 true로 설정

<프로그램 2.5.2> 순환을 이용한 미로 탐색 프로그램

[Location2D.h]

struct Location2D{
    int row; // 현재 위치의 행 번호
    int col; // 현재 위치의 열 번호

    Location2D(int r = 0, int c = 0) {
        row = r;
        col = c;
    }
    
    void set(int r,int c){
        row = r;
        col = c;
    }

    // 위치 p가 자신의 이웃인지 검사하는 함수
    bool isNeighbor(Location2D &p){
        return ((row == p.row && (col == p.col - 1 || col == p.col + 1)) || (col == p.col && (row == p.row - 1 || row == p.row + 1)));
    }

    // 위치 p가 자심과 같은 위치인지를 검사하는 함수(연산자 오버로딩 사용)
    bool operator==(Location2D& p) { return row == p.row && col == p.col; }
};

#include "Location2D.h"
#include <cstdio> 
const int MAZE_SIZE = 6;

char map[MAZE_SIZE][MAZE_SIZE] = {
    { '1', '1', '1', '1', '1', '1' },
    { '0', '0', '1', '0', '0', '1' },
    { '1', '0', '0', '0', '1', '1' },
    { '1', '0', '1', '0', '1', '1' },
    { '1', '0', '1', '0', '0', 'x' },
    { '1', '1', '1', '1', '1', '1' }
};

bool isValidLoc(int r, int c){
    if(r<0 || c <0||r>=MAZE_SIZE||c>=MAZE_SIZE)
        return false;
    else
        return map[r][c] == '0' || map[r][c] == 'x';
}

Location2D locEntry, locExit; // 입구와 출구 위치
bool done = false; // 탐색 성공 여부

// 순환으로 구현한 미로 탐색 구현
void searchRecur(Location2D pt){
    printf("(%d,%d) ", pt.row, pt.col); // 현재 위치 화면에 출력
    if(done)    // 이미 탐색에 성공했다면 return
        return;
    if(pt == locExit){ // 현재 위치가 출구이면 성공
        done = true;
        return;
    }

    int r = pt.row;
    int c = pt.col;
    map[r][c] = '5';

    // 4방향 이웃에 대해 순환 호출
    if(isValidLoc(r-1,c))
        searchRecur(Location2D(r - 1, c));
    if(isValidLoc(r,c-1))
        searchRecur(Location2D(r, c - 1));
    if(isValidLoc(r+1,c))
        searchRecur(Location2D(r + 1, c));
    if(isValidLoc(r,c+1))
        searchRecur(Location2D(r, c + 1));
}

// 미로 탐색 프로그램 주 함수
int main(){
    locEntry.set(1, 0);
    locExit.set(4, 5);
    searchRecur(locEntry); // 미로 탐색 시작
    if(done)
        printf("\n ==> Find Exit.\n");
    else
        printf("\n ==> Not Find Exit.\n");

    return 0;
}