알고리즘 [flood fill]

8 x 8 10 x 10 12 x 12 벽 그리기 채우기

 

 

알고리즘의 기초 중 기초? 라고 볼수있는 flood fill 알고리즘을 알아보자

 

위키백과 에선 플러드필 혹은 시드필 이라고 명명다.

 

내생각엔 알고리즘 의 기본 내용은 정말 간단하다

 

영역을 탐색하고 조건에 맞게 채우면 끝이다.

 

위키백과에서 설명하는 gif 다.

https://en.wikipedia.org/wiki/File:Recursive_Flood_Fill_4_(aka).gif

File:Recursive Flood Fill 4 (aka).gif - Wikipedia

 

4방향 상하좌우 만 순서대로 탐색하며 DFS로 재귀함수를 사용해서 탐색하였을때 위 gif 처럼 차오른다.

 

 

 

enum EMap
{
	Wall,
	Empty,
	Fill
};


// 현재위치에서 이동할 방향
int NextMover[4][2] = { {0,-1} ,{-1,0} ,{1,0},{0,1} };

//채우기 알고리즘 DFS
void FloodFill(vector<vector<EMap>>& map, int x, int y)
{
// 현재 위치 채워주기
	map[x][y] = EMap::Fill;
    
	for (const auto* Move : NextMover) {
	
    	int movex = x + Move[0],
			movey = y + Move[1];
	    //방향 이 배열을 나가지 않는지 확인
    	if (movex <0 || movex >= map.size() || movey < 0 || movey >= map[0].size()) continue;
	    //만약 비워져있다면 탐색 시작
    	if (map[movex][movey] == EMap::Empty) {
			FloodFill(map, movex, movey);
		}
	}

}


vector<string> images = { "■","□","◆"};


int main() {
	vector<vector<EMap>> VectorMap = {
		 {Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Empty,Empty}
		,{Empty,Empty,Empty,Wall,Wall}
		,{Empty,Empty,Empty,Wall,Empty} };

	for (int i = 0; i < VectorMap.size(); ++i) {
		for (int j = 0; j < VectorMap[0].size(); ++j) {
			cout << images[VectorMap[i][j]] << " ";
		}
		cout << "\n";
	}


	int PlayerX = 0, PlayerY = 0;
	FloodFill(VectorMap, PlayerX, PlayerY);

	for (int i = 0; i < VectorMap.size(); ++i) {
		for (int j = 0; j < VectorMap[0].size(); ++j) {
			cout << images[VectorMap[i][j]] << " ";
		}
		cout << "\n";
	}
}​

 

 

 

컴퓨터 그래픽스나 이미지 처리에서 특정 영역을 채우는 데 사용되는 알고리즘이다.

 

페인트 프로그램에서 특정 픽셀을 클릭했을 때 해당 색상을 기준으로 연결된 영역 전체를 새로운 색으로

채우는 기능에 사용할수있다

 

 

 

 

 

해당 알고리즘에서는 채우는게 목적이지만

 

BFS나 DFS 탐색으로 같은 영역을 탐색하는건 다른 알고리즘에서도 정말 많이쓰인다.

 

일전에 작성했던 석유시추 역시 BFS로 탐색하며 해당 영역을 찾아낸다.

 

간단하고 기초적인 알고리즘이지만 정말 많이 쓰인다.

 

https://programing-note.tistory.com/entry/%EC%84%9D%EC%9C%A0%EC%8B%9C%EC%B6%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4LV2

석유시추 [프로그래머스:LV2]

 

 

글쓴이는 일전에 다이렉트 x11로 땅따먹기 게임을 만들때 처음 사용했다.