[알고리즘] maze

미로찾기문제

지나갈 수 있는 통로(pathway) 그리고 벽(wall)이라고 하고 출구를 잡을 때, Recursive Thinking으로 생각할 수 있습니다. 현재 있는 위치에서 출구를 찾는다고 할 때

 

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 이미 가본 곳을 다시 지나지 않고 출구까지 가는 경로가 있거나

boolean findPath(x, y)
{
	if (x, y) is the exit
		return true;
	else
		for each neighbouring cell(x',y') of(x, y) do
			if (x',y') is a pathway cell
				if findPath(x',y')
					return true;
	return false;
}

 

int offset[4][2] = { {-1,0}, {0,1},{1,0},{0,-1} };

void printPath(int x, int y)
{
	print(x, y);
	if (x == N - 1 && y == N - 1)
		return;

	for(int dir=0; dir<4; dir++)
	{
		int x1 = x + offset[dir][0];
		int y1 = y + offset[dir][1];
		if(x1>0 && x1 < N && y1>=0 && y1<N && maze[x1][y1] == PATH_COLOR)
		{
			printPath(x1, y1);
			return;
		}
	}
	printf("No path.");
}

현재 위치를 x y라고 했을 때 경로가 있는 경우에 path color로 coloring 되어 있다고 가정한 후 순서대로 출력하는 함수입니다. 물론 맨 처음ㅇ메 호출할 떄는 x , y 를 0 0  이렇게 입구의 좌표를 주고 하면 됩니다.

 

Blobs 

Binasry 이미지에서 각 픽셀은 background pixel이거나 혹은 image pixel입니다. 서로 연결된 image pixel의 집합을 blob이라고 합니다. 

위 그림은 이와 같이 4개의 blob으로 이루어져있다고 볼 수 있는 것입니다. 

 

입력

-N * N 크기의 2차원 그리드

-하나의 좌표 (x, y)

 

출력

- 픽셀 (x,y)가 포함된 Blob의 크기

- x,y가 어떤 blob에도 속하지 않는 경우에는 0

 

Recursive Thinking

현재 픽셀이 속한 blob의 크기를 카운트하려면 현재 픽셀이 image color가 아니라면 0을 반환한다.

 

현재 픽셀이 image color라면

1. 먼저 현재 픽셀을 카운트한다 (count =1)

2. 현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른 색으로 칠한다.

3. 현재 픽셀에 이웃한 모든 픽셀에 대해서 그 픽셀에 속한 blob의 크기를 카운트하여 카운터에 더해준다.

4. 카운터를 반환한다. 

 

private static int BACKGROUND_COLOR = 0;
private static int IMAGE_COLOR = 1;
private static int ALREADY_COUNTED = 2;

public int countCells(int x, int y)
{
	int result;
	if (x < 0 || x >= N || y < 0 || y >= N)
		return 0;
	else if (grid[x][y] != IMAGE_COLOR)
		return 0;
	else
	{
		grid[x][y] = ALREADY_COUNTED;
		return 1 + countCells(x - 1, y + 1) + countCells(x, y + 1)
			+ countCells(x + 1, y + 1) + countCells(x - 1, y)
			+ countCells(x + 1, y) + countCells(x - 1, y - 1)
			+ countCells(x, y - 1) + countCells(x + 1, y - 1);
	}
}

이 코드는 재귀(Recursion) 를 이용하여 특정 픽셀이 속한 blob(연결된 픽셀 덩어리)의 크기를 계산하는 알고리즘입니다.

알고리즘 개요

• IMAGE_COLOR(1) 값을 가진 픽셀(즉, 찾고자 하는 색상의 픽셀)이 몇 개 연결되어 있는지를 세는 함수입니다.
• DFS(Depth-First Search, 깊이 우선 탐색)를 기반으로 인접한 픽셀들을 탐색하면서 크기를 계산합니다.
• 한 번 방문한 픽셀은 ALREADY_COUNTED(2)로 변경하여 중복 방문을 방지합니다.
• 상하좌우 및 대각선 방향까지 포함하여 총 8방향을 탐색합니다.