간단한 영역 채우기 알고리즘 설계

자료구조설계 - 프로그래밍 설계 프로젝트

1. 제목

간단한 영역 채우기 알고리즘 설계

2. 설계내용

컴퓨터 그래픽에서의 영역 채우기 다음과 같은 흰색 영역이 있을 때 이 영역을 특정한 색으로 채우는 것이다. 여기서 이 영역 안쪽을 검정색으로 채우는 프로그램을 설계하라.

3. 제한조건

2차원 배열이 다음과 같이 되어 있다고 가정하고 영역안의 한 점의 좌표가 주어졌을 경우에 안쪽을 채우는 순환 호출 함수를 작성하여 보라. ×로 표시된 픽셀이 시작 픽셀이다 (순환 호출 함수로 설계)

※ 다음 4. 알고리즘과 5. 프로그램 (소스코드), 6. 실행 결과 및 결론 부분을 작성하시오

[Hint]

위의 문제를 해결하려면 먼저 위의 [그림 2-16] (a)를 2차원 배열을 이용하여 (b)와 같이 나타낸다. 노란색은 2로, 흰색은 0으로 영역을 표시한 다음, 0의 값을 갖는 픽셀을 전부 1로 바꾸면 되는 것이다. 다음 프로그램의 빈칸을 채운 다음, 수행시켜서 어떤 순서대로 채워지는 지를 살펴본다.

#define WHITE 0

#define BLACK 1

#define YELLOW 2

int screen[WIDTH][HEIGHT];

//

char read_pixel(int x, int y)

{

    return screen[x][y];

}

//

void write_pixel(int x, int y, int color)

{

    screen[x][y]=color;

}

// 영역 채우기 알고리즘

void flood_fill(int x, int y)

{

    if (read_pixel (x, y) == WHITE)

    {

        write_pixel (x, y, BLACK);

                                 ;// 순환호출

                                ; // 순환호출

                                ; // 순환호출

                                ; // 순환호출

    }

}

4. 알고리즘 (알고리즘 설명과 흐름도(flow chart))

1. 배열 초기화 하기

전역 변수 screen을 int 형 배열(10x10 크기; 2와 0으로 구성)로 잡고, 미리 초기화 해 둡니다.

2. 초기화 된 배열을 출력(before)

result_print 함수에서 전역 변수(배열) screen을 중첩 for문을 이용, 인덱스 x,y가 9가 될 때까지 screen[i][j]를 출력합니다.

3. 채우기(핵심)

1. flood_fill 함수 호출, screen을 채우는 프로세스를 시작합니다.(x:4 y:4로 시작)
2. read_pixel에 x,y의 값을 넘겨서 screen[x][y]에 대입, 다시 flood_fill 함수에 돌려주어, 그 위치의 값이 WHITE(0)인지 검사(처음 4,4자리에서 시작하기 때문에 YES)합니다.
3. 조건을 만족시키기 때문에 write_pixel 함수를 호출하여 해당 위치를 BLACK(1)로 채우게 됩니다.
4. 다시 flood_fill 함수로 돌아와서 flood_fill(x-1, y)구문을 실행합니다. 반복해서 끝(0)에 도달하면 다음 순환 호출문으로 넘어가는 식으로, flood_fill(x+1, y), flood_fill(x, y-1), flood_fill(x, y+1)을 처리합니다.

// screen 배열을 읽어들이기(순환 호출에서 쓰임)

char read_pixel(int x, int y)

{

    return screen[x][y];

}

// 해당 x, y 위치를 color(BLACK)로 채우기(순환 호출에서 쓰임)

void write_pixel(int x, int y, int color)

{

    screen[x][y] = color;

}

// 영역 채우기 알고리즘 

void flood_fill(int x, int y)

{

    if (read_pixel(x, y) == WHITE) // read_pixel 함수 호출의 결과로 0을 발견하면

    {

        write_pixel(x, y, BLACK); // write_pixel 함수를 호출해서 BLACK(1)로 채우기

        flood_fill(x-1, y); // 순환호출(x-1번째 위치)

        flood_fill(x+1, y); // 순환호출(x+1번째 위치) 

        flood_fill(x, y-1); // 순환호출(y-1번째 위치)

        flood_fill(x, y+1); // 순환호출(y+1번째 위치)

    }

}

4. 변경된 배열을 출력(after)

최종적으로 변경된 screen을 중첩 for문을 이용, 인덱스 x,y가 10이 될 때까지 반복해서 screen[i][j]를 출력합니다.(result_print 함수 재사용)

5. 프로그램 (코드) (코드에 주석 처리)

#include <stdio.h>

#define WHITE 0 // 0을 WHITE라 정의

#define BLACK 1 // 1을 BLACK이라 정의

// [참고] YELLOW는 불필요하여 제거하였습니다.(처음부터 2로 초기화 했습니다)

int screen[10][10]= // 배열 초기화 후 바로 초기값을 넣어줍니다.

          {{2,2,2,2,2,2,2,2,2,2},

           {2,2,2,2,2,2,2,2,2,2},

           {2,2,2,0,0,0,0,2,2,2},

           {2,2,2,2,0,0,0,2,2,2},

           {2,2,2,2,0,0,0,2,2,2},

           {2,2,2,2,0,0,0,0,2,2},

           {2,2,2,2,0,2,2,2,2,2},

           {2,2,2,2,0,2,2,2,2,2},

           {2,2,2,2,0,2,2,2,2,2},

           {2,2,2,2,2,2,2,2,2,2}};

// screen 배열을 읽어들이기(순환 호출에서 쓰임)

char read_pixel(int x, int y)

{

    return screen[x][y];

}

// 해당 x, y 위치를 color(BLACK)로 채우기(순환 호출에서 쓰임)

void write_pixel(int x, int y, int color)

{

    screen[x][y] = color;

}

// 영역 채우기 알고리즘 

void flood_fill(int x, int y)

{

    if (read_pixel(x, y) == WHITE) // read_pixel 함수 호출의 결과로 0을 발견하면

    {

        write_pixel(x, y, BLACK); // write_pixel 함수를 호출해서 BLACK(1)로 채우기

        flood_fill(x-1, y); // 순환호출(x-1번째 위치)

        flood_fill(x+1, y); // 순환호출(x+1번째 위치) 

        flood_fill(x, y-1); // 순환호출(y-1번째 위치)

        flood_fill(x, y+1); // 순환호출(y+1번째 위치)

    }

}

void result_print()

{

      int i, j; // 인덱스 i, j 선언

      for(i=0; i<10; i++) {

            for(j=0; j<10; j++) {

                  printf("%d ", screen[i][j]); // 10x10 크기의 배열 출력(보여주기)

            }

      printf("\n");

      }

}

int main()

{

     printf("영역 채우기 대상 도형\n-------------------\n");

     result_print(); // 초기값으로 지정된 배열을 출력 

     flood_fill(4, 4); // 채우기 실행(시작 위치: 4,4)

     printf("안쪽을 채우는 순환 호출 함수 작동\n-------------------\n");

     result_print(); // flood_fill 함수 호출 뒤 결과(배열) 출력 

     return 0;

}

6. 실행 결과 및 결론

결과 :

screen 배열에서 초기화 했던 값 중 0이 모두 1로 변경되었습니다.

결론:

배열에서, 순환 호출을 이용해서 상(y+1) 하(y-1) 좌(x-1) 우(x+1)를 원하는 값으로 채워 넣을 수 있었습니다.