C언어 - 완전 탐색(Brute-force) 알고리즘으로 map에 있는 구멍 찾기

완전 탐색(Brute-force)이란?

가능한 모든 케이스를 다 검사하는 알고리즘입니다. 모든 케이스를 검사하기 때문에 가장 단순하면서 확실하지만, 시간이 오래 걸릴 수도 있다는 단점이 있습니다.

 

예전에 랜덤한 모양의 2차원 맵을 입력받아, 게임 플레이를 위한 3d맵을 구현하는 프로그램을 작성한 적이 있습니다. 이때, 주어진 맵에 오류가 없는지 검사하는 과정이 필요했는데, 그때 작성했던 알고리즘을 문제로 재구성하여 정리해보았습니다.

 

 

문제 : 맵에 있는 구멍 찾기

랜덤한 모양의 맵이 주어진다고 가정합니다. 이때, 맵이 구멍 없이 벽으로 완전히 둘러싸여 있는지 검사하는 알고리즘을 작성해 봅시다. (맵의 사이즈는 가로 100, 세로 100 이하로만 주어진다고 가정)

정상적인 맵의 예시

맵은 0과 1로 이루어져 있으며, 외부는 ' '공백으로 채워져, 직사각형의 형태를 하고 있습니다. 여기서 1은 벽, 0은 빈 공간을 의미합니다.

다음 조건에 따라, 맵의 유효성을 검사하는 알고리즘을 작성하세요.

- 맵은 char **형으로 주어집니다
- 맵은 벽으로 완전히 둘러싸여 있어야 합니다
- 벽 안에는 최소한 1칸의 빈 공간 '0'이 있어야 합니다
- 벽 안의 공간은 공백없이, '0'과 '1'로 모두 채워져있어야 합니다
- 벽 바깥에는 빈공간 '0'이 있어서는 안 됩니다
- 조건에 모두 맞을 경우 "OK\n", 맞지 않을 경우 "ERROR\n"를 출력합니다

 

 

---

 

풀이

이제 완전 탐색(Brute-force)으로 맵에 있는 구멍을 찾아보겠습니다. 빈 공간인 0으로부터 시작하여, 상하좌우와 대각선 4방향을 포함한 8방향을 검사합니다.

예제에서는 서, 남, 동, 북, 북서, 남서, 남동, 북동 순으로 검사합니다.

벽인 1을 만나면 구멍이 없는 것이니, return하여 이전 위치로 돌아가 검사를 마저 이어나갑니다. 또, 다른 빈 공간 0을 만나게 되면 x로 체크하고, check_map()을 재귀 호출하여, 현재 위치로부터 다시 8방향을 검사합니다. (이미 체크한 부분을 다시 방문했을 때, 검사를 반복하지 않기 위함)

 

검사 도중, 벽을 만나지 못해 ' '공백에 도달하게 되면 "ERROR\n"를 출력합니다.

그리고 공백을 만나지 않고 모든 루프가 종료되면, 벽에는 구멍이 없으므로 "OK\n"를 출력합니다.

 

 

아래 check_map()은 완전 탐색으로 맵을 검사하는 핵심 함수입니다.

#include <unistd.h>
#include <stdlib.h>

int	g_dirx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}; //서, 남, 동, 북, 북서, 남서, 남동, 북동
int	g_diry[8] = {0, 1, 0, -1, -1, 1, 1, -1};

/* 완전 탐색으로 맵을 검사한다 */
int	check_map(char **map, int x, int y)
{
	int i;

	if (map[y][x] == '1' || map[y][x] == 'x')
		return (1);
	if (map[y][x] == ' ')	//공백을 만나 0 return
		return (0);
	map[y][x] = 'x';	//이미 방문한 곳은 x로 체크
    
	/* 0을 만나 함수를 재귀 호출 */
	i = -1;
	while (++i < 8)
		if (check_map(map, x + g_dirx[i], y + g_diry[i]) == 0) //g_dirx와 g_diry로 8방향 이동
			return (0);
	return (1);
}

이때, g_dirx와 g_diry와 같은 방향을 나타내는 배열을 이용하면, while문으로 손쉽게 8방향을 모두 조회할 수 있습니다.

 

 

다음은 util함수들입니다.

/* seg fault 방지를 위해, 맵의 테두리를 ' '공백으로 감싼다 */
char	**init_map(char **map)
{
	int		x;
	int		y;
	char	**test_map;

	/* 테두리 공간을 확보하기 위해 가로,세로가 2씩 큰 맵 생성 */
	if (!(test_map = (char **)malloc(sizeof(char *) * 103)))
		return (0);
	test_map[102] = 0;	//null
	y = -1;
	while (++y < 102)
	{
		if (!(test_map[y] = (char *)malloc(sizeof(char) * 103)))
			return (0);
		test_map[y][102] = 0;	//null
		x = -1;
		while (++x < 102)
			test_map[y][x] = ' ';	//공백으로 채움
	}

	/* 테두리는 공백으로 남겨두고, (1, 1)부터 map데이터를 채움 */
	y = -1;
	while (map[++y])
	{
		x = -1;
		while (map[y][++x])
			test_map[y + 1][x + 1] = map[y][x];
	}
	return (test_map);
}

/* char **를 free하는 함수 */
int		free_map(char **map, int cnt)
{
	while (cnt >= 0)
	{
		free(map[cnt]);
		cnt--;
	}
	free(map);
	return (0);
}

init_map()은 맵의 테두리를 공백으로 감싸주는 함수입니다. 테두리를 감싸주면, 맵 검사 중 char** 범위를 벗어난 인덱스를 참조하여, seg fault가 발생하는 것을 방지할 수 있습니다.

맵의 사이즈는 최대 100x100이라고 가정했으므로, 100+2의 사이즈의 맵을 생성 합니다.

(그 외에, check_map()함수 내에서 맵의 사이즈를 벗어난 인덱스를 조회하려 하면, 0을 return하도록 예외 처리하는 방법도 있습니다. 차후에 이 방법으로 수정하여 재 업로드할 예정입니다.)

 

 

마지막으로 메인 함수입니다. 테스트를 위해 임의로 맵을 작성 해 두었습니다.

int	main()
{
	int		x, y;
	int		is_zero;
	char	**map;
	char	**test_map;

	/* 예시 문제 */
	if (!(map = (char **)malloc(sizeof(char *) * 15)))
		return (0);
	map[0] = "        1111111111111111111111111";
	map[1] = "111111111000000000110000000000001";
	map[2] = "101100000111000000000000111111111";
	map[3] = "1001000000000000000000001        ";
	map[4] = "111111111011000001110000111111111";
	map[5] = "100000000011000001110111111110001";
	map[6] = "111101111111110111000000100011111";
	map[7] = "11110111111111011101010010001    ";
	map[8] = "11100000110101011100000010001    ";
	map[9] = "  100000000000011000000100001    ";
	map[10]= "11100000000000001101010010001    ";
	map[11]= "1100000000010101111101111010111  ";
	map[12]= "11110100111110101 101111010001   ";
	map[13]= "111111111 1111111 111111111111   ";
	map[14]= 0;

	/* 테스트 시작 */
	test_map = init_map(map);
	free(map);
	is_zero = 0;
	y = -1;
	while (test_map[++y])
	{
		x = -1;
		while (test_map[y][++x])
			if (test_map[y][x] == '0')	//'0'을 만나면 검사 시작
			{
				is_zero = 1;
				if (check_map(test_map, x, y) == 0)
				{
					write(1, "ERROR\n", 6);
					free_map(test_map, 103);
					return (0) ;
				}
			}
	}
	if (is_zero == 0)
		write(1, "ERROR\n", 6);
	else
		write(1, "OK\n", 3);
	free_map(test_map, 103);
	return (0);
}

 

실행 결과

check_map() 실행 전과 실행 후