[Hive Helsinki / Piscine] BSQ

 극악의 난이도로 유명한 BSQ, 굳이 도전하지 않는 사람도 많았고, 성패가 딱히 합격에 영향을 미치지 않는 듯싶은 프로젝트였다. (당연하다. 아무도 통과하지 못하기 때문이다.) 

 그래도 계속 c 프로젝트만 하고 있기에는 c 프로젝트의 난이도가 대체로 초심자에 맞춰 형성되어 있어서 나한테는 단순 반복 같이 느껴질 때가 많았다. rush 프로젝트들을 통과하지는 못했지만 하면서 가장 재밌다고 느꼈기 때문에, bsq 시작 전에 최대한 c 진도를 합격자들과 비슷하게 맞춰두고 남은 시간을 bsq에 쏟았다. 

 

 결론부터 말하자면, 통과하지 못할 코드로 팀원까지 두 번의 긴 평가를 받게 하기는 너무 미안해서 한 번 평가를 받은 후 포기했다. 여기에 게시하는 코드는 피신 이후 내가 수정한 코드이다. 

 그리고 끝까지 날 괴롭히던 문제가 있었는데, 바로 뜬금없는 위치에서 발생하는 segmentation fault였다. 여기서 절대 발생할리가 없는데..? 싶은 부분에서 반복적으로 segmentation fault가 발생했다. 입력되는 map의 크기가 일정 이상으로 클 때만 발생하길래 뭔가 코드에 잘못된 부분이 있나 싶어 디버깅을 계속 시도했지만, 아무리 봐도 segmentation fault가 발생할 수 없는 부분에서 끊기는 것을 확인했다. 

 진짜 segmentation fault에 대해서 공부하다시피 서칭을 해본 결과, compiler optimization 문제라는 것을 알게 되었다. compiler의 optimization 값이 너무 높을 경우 segmentation fault가 발생할 수 있다고 한다. 따라서 -O2 플래그로 낮은 레벨로 설정하여 컴파일하니 잘 작동했다. 42에서 시스템이 코드를 확인할 때도 이렇게 컴파일해야만 실행되는 코드가 통과될지는 알 수 없지만, 개인적으로 해결하고 싶은 문제였으니 만족한다.

 

 BSQ는 주어진 map의 빈 부분에 만들 수 있는 가장 큰 정사각형을 넣어서 다시 출력하는 과제였다. 까다로웠던 부분은 map 파일이 주어지지 않는 경우는 standard input으로 터미널에서 입력을 받아야 하는 것이었다. map의 크기가 완전히 주어지지 않은 상태에서 먼저 크기를 파악해야 map 배열을 만들 수 있는데, 한 번 데이터를 읽고 나면 다시 읽을 수 없으니 문제였다. 그래서 크기가 맞을 때까지 메모리를 포인터 변수에 계속 재할당하면서 입력받았다. 

 

 BSQ의 경우 프로젝트 자체가 워낙 길고 복잡하기 때문에 간단히 내가 사용한 대략적인 방법만 소개하려 한다. 나는 주어진 map의 크기에서 만들 수 있는 가장 큰 정사각형부터 시작해서 해당 정사각형을 각 위치를 순회하며 넣을 수 있는지를 확인하고, 넣지 못하는 경우에는 크기를 하나씩 줄여가면서 쭉 탐색하는 방식을 선택했다. 위치를 탐색할 때는 만약 불가능한 경우라면, 해당 범위 내에 있는 가장 오른쪽에 있는 장애물의 위치를 파악하여 그다음 위치부터 다시 탐색할 수 있도록 했다. 

 

 다음은 내가 작상한 코드이다. 코드 내에 세세한 설명은 주석으로 달아두었다. 

main.h

#ifndef MAIN_H
# define MAIN_H

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

// map 형성을 위한 정보를 담은 구조체
typedef struct INFO
{
	unsigned int	x;	// map row 개수
	unsigned int	y;  // map column 개수
	char			empt;	// empty 문자
	char			obst;	// obstacle 문자
	char			full;	// full 문자
}	t_info;

// 결과값을 담은 구조체
// -> x, y 좌표에서 시작하는 size 길이의 변을 가진 정사각형의 결과값
typedef struct RESULT
{
	unsigned int	size;
	unsigned int	x;
	unsigned int	y;
}	t_result;

// main.c
void		print_map(char **map, t_info info);
void		print_res(t_result res, char **map, t_info info);

// ft_func.c
void			ft_putstr(char *str);
unsigned int	ft_atoi(char *str, int len);
unsigned int	count_line(int infile);
void			ft_strncpy(char *dest, char *src, unsigned int n);

// file_map.c (파일 입력 받았을 때 map 만드는 함수)
char			**make_file_map(char *path, t_info *info);
int				fill_file_info(char	*path, t_info *info);

// std_map.c (std 입력 받았을 때 map 만드는 함수)
char		**make_std_map(t_info *info);
int				fill_std_info(t_info *info);
void			set_info(t_info *info, int i, char signs[3]);
char			**fill_map(t_info *info, unsigned int x);
unsigned int	make_first_line(t_info *info, char **line, unsigned int size);

// ft_map.c (map 만들 때, file과 std에서 공통으로 사용되는 helper function)
void			set_chars(t_info *info, char e, char o, char f);
char	*map_array(int infile, unsigned int x, t_info *info);
int				is_allowed(char c, t_info *info);

// square.c (결과값인 정사각형을 찾는 함수)
t_result		find_square(char **map, t_info info);
int				recur_square(t_result *res, char **map, t_info info);
unsigned int	check_obst(t_result *res, char **map, char obst);

#endif

 

main.c 

#include "main.h"

int	main(int argc, char **argv)
{
	t_info		info;
	char		**map;
	t_result	res;

	if (argc == 1)	// parameter로 파일명을 안받은 경우 = map을 터미널 입력으로
		map = make_std_map(&info);
	else if (argc == 2)  // parameter로 파일명을 받은 경우
		map = make_file_map(argv[1], &info);
	else
	{
		ft_putstr("map error\n");
		exit(1);
	}

	if (map == NULL)  // map 만드는 데에 실패한 경우
	{
		ft_putstr("map error\n");
		exit(1);
	}

	// 결과값 찾기
	res = find_square(map, info);
	printf("find square complete: x=%d, y=%d, size=%d\n", res.x, res.y, res.size);
	if (res.size == 0)	// 결과값 찾기에 실패한 경우는 map 자체 출력
		print_map(map, info);
	else	// 결과 찾기에 성공했다면 결과 출력
		print_res(res, map, info);
}



void	print_map(char **map, t_info info)
{
	unsigned int	x;
	unsigned int	y;

	x = 0;
	while (x < info.x)
	{
		y = 0;
		while (y < info.y)
		{
			write(1, &(map[x][y]), 1);
			y++;
		}
		x++;
		write(1, "\n", 1);
	}
}

void	print_res(t_result res, char **map, t_info info)
{
	unsigned int	x;
	unsigned int	y;

	printf("x:%d, y:%d, size:%d | %c\n", res.x, res.y, res.size, info.full);
	x = 0;
	while (x < info.x)
	{ y = 0;
		while (y < info.y)
		{
			if (x >= res.x && x < (res.x + res.size))
			{
				if (y >= res.y && y < (res.y + res.size))
				{
					write(1, &(info.full), 1);
					y++;
					continue ;
				}
			}
			write(1, &(map[x][y]), 1);
			y++;
		}
		write(1, "\n", 1);
		x++;
	}
}

 

ft_func.c 

#include "main.h"

void	ft_putstr(char *str)
{
	while (*str)
		write(1, str++, 1);
}

unsigned int	ft_atoi(char *str, int len)
{
	int				i;
	unsigned int	res;

	i = 0;
	res = 0;
	while (i < len)
	{
		if (str[i] < '0' || str[i] > '9')
			return (0);
		res = res * 10 + str[i] - '0';
		i++;
	}
	return (res);
}

unsigned int	count_line(int infile)
{
	char	c;
	unsigned int		len;

	len = 0;
	while (read(infile, &c, 1) > 0 && c != '\n')
		len++;
	return (len);
}

void	ft_strncpy(char *dest, char *src, unsigned int n)
{
	unsigned int	i;

	i = 0;
	while (i < n)
	{
		dest[i] = *src;
		i++;
		src++;
	}
}

 

ft_map.c 

#include "main.h"

void	set_chars(t_info *info, char e, char o, char f)
{
	info->empt = e;
	info->obst = o;
	info->full = f;
}

// infile에 있는 map 중 x번째 row를 하나의 문자열로 만들어 리턴
// std일 때는 infile을 0으로, file일 때는 해당 파일 정보를 넣어서 실행
char	*map_array(int infile, unsigned int x, t_info *info)
{
	char			*array;
	char			c;
	unsigned int	y;

	// column만큼 메모리 할당
	array = (char *)malloc(sizeof(char) * (info->y));
	if (array == NULL)
		return (NULL);

	// column만큼 반복하며 한글자씩 채우기
	y = 0;
	while (y < info->y)
	{
		if (read(infile, &c, 1) < 0 || !is_allowed(c, info))
			return (NULL);
		array[y++] = c;
	}
	if (x != (info->x - 1) && (read(infile, &c, 1) < 0 || c != '\n'))
		return (NULL);
	return (array);
}

int	is_allowed(char c, t_info *info)
{
	if (c != info->empt && c != info->obst && c != info->full)
		return (0);
	if (c < 32 || c > 126)
		return (0);
	return (1);
}

 

std_map.c 

#include "main.h"

char	**make_std_map(t_info *info)
{
	// map 만들기 전 기본 정보 채우기에 실패하면 0 리턴
	if (fill_std_info(info) == 0)
		return (NULL);
	if (info->x == 0)
		return (NULL);

	// fill_map() 함수로 만든 map 바로 리턴
	return (fill_map(info, 1));
}

int	fill_std_info(t_info *info)
{
	char	c;
	char	signs[3];
	int		i;

	// 숫자에 해당 하는 부분을 int type으로 변환하여 row 정보 입력
	info->x = 0;
	while (read(0, &c, 1) > 0 && c >= '0' && c <= '9')
		info->x = (info->x) * 10 + c - '0';

	// 나머지 문자는 sign 배열에 하나씩 저장
	signs[0] = c;
	i = 1;
	while (i < 3 && c != '\n' && read(0, &c, 1) >= 0)
		signs[i++] = c;

	// 만약 sign 배열이 다 채워졌는데, 
	// 다음 문자가 존재하지 않거나, 한 문장이 끝나지 않은 경우 0 리턴
	if (i == 3 && (read(0, &c, 1) < 0 || c != '\n'))
		return (0);

	// 앞서 입력 받은 정보들로 info 구조체 채우기
	set_info(info, i, signs);

	// map이 존재할 수 없는 상황(row가 0)이거나 
	// obstacle, full, empty 문자 중 같은 문자가 있다면 0 리턴
	if (info->x == 0 || info->obst == info->full)
		return (0);
	if (info->empt == info->obst || info->empt == info->full)
		return (0);
	return (1);
}

void	set_info(t_info *info, int i, char signs[3])
{
	if (i == 3)	// 문자 세개 다 채워진 채로 온 경우
		set_chars(info, signs[0], signs[1], signs[2]);
	else if (i == 2) // 문자가 두개만 채워진 경우 -> x로 넣었던 마지막 숫자가 사실 empty문자
	{
		set_chars(info, ((info->x) % 10 + '0'), signs[0], signs[1]);
		(info->x) /= 10;
	}
	else if (i == 1) // 문자가 하나만 채워진 경우 -> x로 넣었던 마지막 두 개 숫자가 사실 empty와 obstable 문자
	{
		set_chars(info, 0, ((info->x) % 10 + '0'), signs[0]);
		(info->x) /= 10;
		info->empt = (info->x) % 10 + '0';
		(info->x) /= 10;
	}
	else  // 문자가 하나도 채워지지 않은 경우 -> x로 넣었던 마지막 숫자 세개가 사실 empty, obstabcle, full 문자
	{
		info->full = (info->x) % 10 + '0';
		(info->x) /= 10;
		info->obst = (info->x) % 10 + '0';
		(info->x) /= 10;
		info->empt = (info->x) % 10 + '0';
		(info->x) /= 10;
	}
}

char	**fill_map(t_info *info, unsigned int x)
{
	char	**map;

	// row만큼 메모리 할당
	map = (char **)malloc(sizeof(char *) * (info->x));
	if (map == NULL)
		return (NULL);

	// 첫번째 row 입력받으면서 colum 수 파악
	info->y = make_first_line(info, &(map[0]), 0);
	if (info->y == 0)
	{
		free(map);
		return (NULL);
	}

	// row 하나씩 채우기
	while (x < info->x)
	{
		printf("x=%d\n", x);
		map[x] = map_array(0, x, info);
		if (map[x] == NULL)
		{
			while (x > 0)
				free(map[--x]);
			free(map);
			return (NULL);
		}
		x++;
	}
	return (map);
}

// std 입력에서 첫 번째 줄의 길이를 알아내기 위해 첫번째줄만 따로 입력받는 함수
// 첫번째 줄의 크기에 맞을 때까지 재귀를 통해 배열의 크기를 10씩 늘려가면서 입력받는다
unsigned int	make_first_line(t_info *info, char **line, unsigned int size)
{
	char			c;
	char			*res;
	unsigned int	i;

	// res 배열에 size + 10의 메모리를 할당
	res = (char *)malloc(sizeof(char) * (size + 10));
	if (res == NULL)
		return (0);

	// 현재까지 line 배열에 입력되어있는 문자들을 res 배열로 옮김
	if (size > 0)
	{
		ft_strncpy(res, *line, size);
		free(*line);
	}

	i = size;
	while (i < (size + 10))
	{
		if (read(0, &c, 1) < 0 || c == '\n') {
			*line = res;
			return (i);
		}
		if (!is_allowed(c, info))
			return (0);
		res[i++] = c;
	}

	// 기존 line 배열을 size가 10 커진 res배열로 대체
	*line = res;

	// size를 증가시켜 재귀
	return (make_first_line(info, line, size + 10));
}

 

ft_map.c 

#include "main.h"

void	set_chars(t_info *info, char e, char o, char f)
{
	info->empt = e;
	info->obst = o;
	info->full = f;
}

// infile에 있는 map 중 x번째 row를 하나의 문자열로 만들어 리턴
// std일 때는 infile을 0으로, file일 때는 해당 파일 정보를 넣어서 실행
char	*map_array(int infile, unsigned int x, t_info *info)
{
	char			*array;
	char			c;
	unsigned int	y;

	// column만큼 메모리 할당
	array = (char *)malloc(sizeof(char) * (info->y));
	if (array == NULL)
		return (NULL);

	// column만큼 반복하며 한글자씩 채우기
	y = 0;
	while (y < info->y)
	{
		if (read(infile, &c, 1) < 0 || !is_allowed(c, info))
			return (NULL);
		array[y++] = c;
	}
	if (x != (info->x - 1) && (read(infile, &c, 1) < 0 || c != '\n'))
		return (NULL);
	return (array);
}

int	is_allowed(char c, t_info *info)
{
	if (c != info->empt && c != info->obst && c != info->full)
		return (0);
	if (c < 32 || c > 126)
		return (0);
	return (1);
}

 

file_map.c

#include "main.h"

char	**make_file_map(char *path, t_info *info)
{
	char			**map;
	int				infile;
	unsigned int	x;

	// 기본 정보 채우기에 실패할 경우 NULL 리턴 (잘못된 입력)
	if (fill_file_info(path, info) == 0)
		return (NULL);

	// empty, obstacle, full 문자들 간 중복 존재할 경우 NULL 리턴 (잘못된 입력)
	if (info->empt == info->obst || info->empt == info->full)
		return (NULL);
	if (info->obst == info->full)
		return (NULL);

	// 파일 열고 메모리 할당
	infile = open(path, O_RDONLY);
	map = (char **)malloc(sizeof(char *) * info->x);
	if (infile < 0 || map == NULL)
		return (NULL);

	// count_line() 함수 이용해서 단순히 이미 info 파악 위해 읽었던 첫 줄 skip
	count_line(infile);

	// 한 줄씩 map 채우기
	x = 0;
	while (x < info->x)
	{
		map[x] = map_array(infile, x, info);
		if (map[x] == NULL)
			return (NULL);
		x++;
	}
	return (map);
}

// 기본적인 map에 대한 정보를 담은 info 구조체 채우기
// 여기서 한 번 파일을 읽고 map을 읽어들일 때는 파일을 다시 연다.
int	fill_file_info(char *path, t_info *info)
{
	int				infile;
	char			c;
	char			*info_line;
	unsigned int	len;

	// 파일을 열어서 첫번째 줄의 길이를 센다
	infile = open(path, O_RDONLY);
	if (infile < 0)
		return (0);
	len = count_line(infile);

	// 첫번째 줄의 길이만큼 할당한 배열을 만든다
	info_line = (char *)malloc(sizeof(char) * (len + 1));
	
	// 파일을 다시 열어 만든 배열에 첫번째 줄을 복사해 넣는다
	infile = open(path, O_RDONLY);
	if (infile < 0)
		return (0);
	len = 0;
	while (read(infile, &c, 1) > 0 && c != '\n')
		info_line[len++] = c;

	// info를 채워넣는다
	set_chars(info, info_line[len-3], info_line[len-2], info_line[len-1]);
	info->x = ft_atoi(info_line, len-3);

	// y는 다시 다음 줄의 길이를 세서 넣음
	info->y = count_line(infile);
	close(infile);

	if (info->x == 0 || info->y == 0)
		return (0);
	return (1);
}

square.c 

#include "main.h"

t_result	find_square(char **map, t_info info)
{
	t_result	res;

	// Min(info.x, info.y)로 res.size 설정 (가능한 가능 큰 정사각형부터 탐색 시작)
	res.size = info.x;
	if (res.size < info.y)
		res.size = info.y;
	
	// 좌표 (0, 0)부터 탐색 시작
	res.x = 0;
	res.y = 0;

	// recur_square() 함수로 결과값을 찾으면 바로 리턴
	if (recur_square(&res, map, info))
		return (res);

	// 못 찾았다면 res.size를 0으로 하여 리턴
	res.size = 0;
	return (res);
}

int	recur_square(t_result *res, char **map, t_info info)
{
	int		obst_loc;

	// size가 0이라는 것은 가능한 정사각형 경우의 수를 모두 탐색했으나 결과 x이므로 바로 리턴
	if (res->size <= 0)
		return (0);
	// 해당 size로 가능한 경우가 없다면 size를 감소시키고 (0, 0)부터 재탐색 시작
	if (res->x + res->size > info.x)
	{
		--(res->size);
		res->x = 0;
		res->y = 0;
		return (recur_square(res, map, info));
	}
	// 가로로 이동하며 탐색을 완료했으면 한칸 아래로 내려가서 다시 탐색 시작
	if (res->y + res->size > info.y)
	{
		++(res->x);
		res->y = 0;
		return (recur_square(res, map, info));
	}

	obst_loc = check_obst(res, map, info.obst);
	if (obst_loc >= 0)
	{
		res->y = obst_loc + 1;
		return (recur_square(res, map, info));
	}
	return (1);
}

unsigned int	check_obst(t_result *res, char **map, char obst)
{
	unsigned int	x;
	unsigned int	y;

	y = res->y + res->size;
	while (y > res->y)
	{
		y--;
		x = res->x + res->size;
		while (x > res->x)
		{
			x--;
			if (map[x][y] == obst)
				return (y);
		}
	}
	return (-1);
}

 

make file

CC = cc
FLAGS = -Wall -Wextra -Werror
SRC_DIR = ./srcs
INCLUDE = -Iincludes/

SRCS = main.c map.c ft_func.c square.c
OBJECTS = $(SRCS:.c=.o)
OBJS = $(patsubst %.o, $(SRC_DIR)/%.o, $(OBJECTS))
TARGET = bsq

all: $(TARGET)

$(SRC_DIR)/%.o: $(SRC_DIR)/%.c
	$(CC) $(FLAGS) $(INCLUDE) -c $^ -o $@

$(TARGET): $(OBJS)
	$(CC) $^ -o $@

clean:
	rm -f $(OBJS)

fclean: clean
	rm -f $(TARGET)

re : fclean all

.PHONY: all clean fclean re