[42서울] so_long 맵 유효성 검사(BFS)

서론

이번엔 42서울 2서클까지의 과제들 중 리트라이를 가장 많이 했던(무려 5번..!) so_long에 대한 글을 서보려고 한다. so long은 지도가 그려진 파일을 입력받아 클리어 가능하다면 화면에 게임을 출력하는 과제이다. 지도 파일의 예시는 다음과 같다.

• 0은 빈공간,
• 1은 벽,
• C는 수집품,
• E는 맵의 출구,
• P는 주인공의 시작지점이다.

주인공은 모든 수집품을 모아야 맵의 출구로 나갈 수 있다. 그 전에는 출구 위로 지나갈 수 없다.

구현

main

so_long의 시작이다. argv의 인자로 .ber 확장자인 파일 이름을 입력받는다. 입력받은 파일은 so_long 게임의 지도(map)가 된다. 이전에 so_long 평가를 갔었는데 main 문에 핵심 로직이 다 담기며 가독성이 좋고 간결한 코드를 보게 되어 영감을 받아 이런 코드를 작성하게 되었다. 다음은 각 함수에 대한 간단한 설명이다.

• check_arg_and_get_fd: 인자의 정당성을 검사하고 유효한 fd 값을 반환한다.
• get_map: fd 값으로 파일을 읽어서 2차원 배열 map을 반환한다.
• check_map: map의 정당성을 검사한다.
• start_grapic: map을 화면에 출력하고 게임을 시작한다.

 

check_arg_and_get_fd

인자의 개수 검사, 확장자 검사, 인자로 받은 파일을 열어 fd 리턴의 기능을 순서대로 수행한다.

 

get_map

이전에 구현했던 get_next_line 함수를 활용하여 fd 값에서 한줄씩 읽어서 2차원 배열 map을 구한다. strjoin을 사용하고 메모리 해제를 해주지 않아서 평가에서 fail 받은 적이 있었다. 메모리 누수 항상 조심하자. ft_strdup 함수를 사용해서 줄 수를 줄이는 것은 팁이다.

 

check_map

 

map의 유효성을 검사한다. map의 가장자리가 1로 채워져 있는지(1은 벽을 의미), map이 직사각형 모양인지 검사한다.

check_map_contents에서는 c, e, p(coin, end, player)의 개수가 적절한지 검사한다.

check_map_validation에서는 map이 클리어 가능한지 검사한다.

 

check_map_validation

 

map이 클리어 가능한지 검사한다. 플레이어(P)는 모든 코인(C)를 수집할 수 있어야 하며 도착지(E)에 도달할 수 있어야 한다. 플래이어가 모든 코인을 수집할 수 있는지에 대해서는 BFS(너비 우선 탐색)를 사용하여 체크하였다. 특이한 점이 있다면 플레이어가 아닌 코인과 도착지로부터 시작한 BFS 방식의 탐색을 하였다. 

만약 위와 같은 맵이 존재한다고 가정하자. 플레이어는 모든 C를 모으기 전에 E를 지날 수 없으므로 유효하지 않은 맵이다. 이러한 맵에 대한 유효성을 올바르게 검사하기 위해 C와 E를 대상으로 P를 찾는 BFS를 수행하였다(C로부터 시작한 탐색의 경우 E를 벽으로 간주). 어짜피 C, E 모두 P와 연결되어 있어야 유효한 맵이기 때문에 E와 C로부터 P를 찾는 탐색을 해도 된다.

 

+) 나중에 생각해보니 P로 한번만 탐색할 것을 E와 C로도 탐색하여 비효율적인 코드라는 것을 알게 되었다. ㅜㅜ. 만약 P로 탐색을 한다면 모든 C를 수집하기 전까지 E를 벽으로 간주하여 탐색을 하면 될 것 같다.

 

BFS는 자료구조 queue를 사용하여 구현했다.

[자료구조] 연결 리스트 4 (연결 스택과 큐, 다항식, 이중 연결 리스트)

 

후기

다음 포스팅은 so_long 과제의 그래픽에 대한 내용이다.