Chater 4-2. 플러드 필 알고리즘 구현 (스택 사용)

홍정모 교수님의 강의 홍정모의 따라하며 배우는 C언어(부록) 를 듣고 정리한 필기입니다. 😀 ppt 캡처는 모두 교수님 강의에서 캡처한 것임을 밝힙니다.

Chapter 4. 스택

🚀 플러드 필 알고리즘이란? (Flood Fill)

플러드 필 위키피디아

하얀 곳은 갈 수 있는 곳, 파란 곳은 벽이라 갈 수 없는 곳이다. BFS과 비슷하게 이동은 스택에서 빼내는(Pop) 것으로 이루어지고, 현재 위치에서 갈 수 있는 곳들은 스택에 넣는다.(Push)

이 과정을 스택이 빌 때까지 진행하면 출발지에서 갈 수 있는 곳은 모두 방문하게 된다. 출발을 좌하단 (0,0) 에서 시작한다면 바깥 하얀 부분을 모두 방문하게 될 것이고, 출발을 가운데 하얀 부분에서 한다면 가운데 하얀 부분은 모두 방문하게 될 것이다.

갈 수 있는 곳은 스택에 넣어버린다. 그리고 갔다면 pop 함 그 pop 한 것을 기준으로 갈 수 있는 곳들을 push 한다. 스택이 다 비면 종료.(= 더 이상 갈 곳이 없음)

1. Pop 👉 방문
2. Push 👉 현재 방문한 곳에서 갈 수 있는 곳들 스택에 넣기

스택은 먼저 들어가는게 제일 나중에 나온다.

상👉하👉좌👉우 이 순서로 갈 수 있는 곳을 검사한다면 위와 같은 순서로 방문하게 되며(출발지의 밑에 있는게 오른쪽에 있는 것 보다 먼저 스택에 들어가게 되니까) 가장 먼저 스택에 들어갔었던 (0, 1)은 가장 마지막에 방문하게 된다. 어떤 방향부터 검사하느냐에 따라 방문 순서가 달라질 것이다.

📜element.h

typedef struct
{
	int i;
  int j;
}element;

📜stack.h

📜main.c

#include <conio.h>
#include "stack.h"

#define WIDTH 7
#define HEIGHT 7

static int map[HEIGHT][WIDTH] = {
	0, 0, 0, 0, 0, 0, 0,
	0, 1, 1, 1, 1, 1, 0,
	0, 1, 0, 0, 0, 1, 0,
	0, 1, 0, 0, 0, 1, 0,
	0, 1, 0, 0, 0, 1, 0,
	0, 1, 1, 1, 1, 1, 0,
	0, 0, 0, 0, 0, 0, 0
};

void print_map()
{
	for (int j = 0; j < HEIGHT; ++j) {
		for (int i = 0; i < WIDTH; ++i)
			printf("%d ", map[j][i]);
		printf("\n");
	}
	printf("\n");
}

element get_element(const int i, const int j)
{
	element new_element;
	new_element.i = i;
	new_element.j = j;
	return new_element;
}

print_stack(const Stack* stack)
{
	printf("Stack : ");
	if (IsEmpty(stack) == true)
		printf("Empty");
	else
		for (int i = 0; i <= stack->top; ++i)
			printf("(%d, %d) ", stack->items[i].i, stack->items[i].j);
	printf("\n");
}

int main()
{
	print_map();

	Stack to_visit;
	Initialize(&to_visit);

	Push(&to_visit, get_element(0, 0)); // start cell  (바깥 쪽 하얀색)
	// Push(&to_visit, get_element(3, 3)); // start cell (안 쪽 하얀색)

	while (IsEmpty(&to_visit) != true) {
		
		element cell = Pop(&to_visit);

		if (map[cell.j][cell.i] == 1) // already visited
			continue;

		map[cell.j][cell.i] = 1; // 방문 처리

		// 현재 방문 중인 위치에서 갈 수 있는 곳들 스택에 넣기 (상하좌우)
		if (cell.j - 1 >= 0 && map[cell.j - 1][cell.i] == 0) // up
			Push(&to_visit, get_element(cell.i, cell.j - 1));

		if (cell.j + 1 < HEIGHT && map[cell.j + 1][cell.i] == 0) // down
			Push(&to_visit, get_element(cell.i, cell.j + 1));

		if (cell.i - 1 >= 0 && map[cell.j][cell.i - 1] == 0) // left
			Push(&to_visit, get_element(cell.i - 1, cell.j));

		if (cell.i + 1 < WIDTH && map[cell.j][cell.i + 1] == 0) // right
			Push(&to_visit, get_element(cell.i + 1, cell.j));

    // 애니메이션 효과로 출력
		system("cls"); // #include <conio.h> 에서 지원하는, 콘솔창 지우는 명령어! (clear screen 의 약자) system(커맨드)
		print_all(&to_visit);
		printf("Cell : (%d, %d)\n", cell.i, cell.j);
		print_map();
		int dummy = _getch(); // 사용자가 엔터 쳐야 다음으로 넘어가게끔
	}

	printf("Result:\n");
	print_map();
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

DataStructure2 카테고리 내 다른 글 보러가기