so_long 과제에서,
플레이어 위치부터 출구 까지 도달 가능한지 경로 유효성을 판단해야 한다.
11111
100E1
10001
10001
1P001
11111
C++
복사
DFS or BFS?
bfs를 선택 할 이유가 없음.
재귀를 쓸 필요도 없고, stack을 써서 dfs를 돌리면 된다.
지역변수로 stack 배열 메모리를 잡고 싶으나,
맵 최대사이즈가 명시된 것이 없으므로 성능을 포기하고 malloc하여 메모리 잡기.
(사실 인라인 어셈으로 push/pop 써서 구현해도 된다. 빠르고 가변적이다)
t_xy *const stack = malloc(game->map_col * game->map_row * sizeof(t_xy));
int top;
C++
복사
if (get_obj(game, now.row + 1, now.col) == '0') // up
push(stack, &top, now.row + 1, now.col);
if (get_obj(game, now.row - 1, now.col) == '0') // down
push(stack, &top, now.row - 1, now.col);
if (get_obj(game, now.row, now.col + 1) == '0') // left
push(stack, &top, now.row, now.col + 1);
if (get_obj(game, now.row, now.col - 1) == '0') // right
push(stack, &top, now.row, now.col - 1);
C
복사
“한 칸은 여러 번 stack에 들어갈 수 없다.”
라고 정하고 구현하면 stack 크기는 맵 최대 크기를 넘을 수 없다.
IS_VISITED
이제 필요한 것은 “여기 방문한 적이 있던가” 를 저장해야 하는데,
malloc 한 번 더 하기가 싫다…
자. map은 char로 이루어져 있다.
extended ascii가 아니라면 제일 왼쪽 sign 비트를 사용하지 않는다.
제일 왼쪽 비트를 is_visited 플래그로 쓰면 된다.
이러면 추가 할당은 필요하지 않는다.
#define MSB (0x80) // (1 << (CHAR_BIT - 1))
// 방문
map[i][j] |= MSB;
// 방문 판단
if ((map[i][j] & MSB) != 0)
{
// 기존 글자
return map[i][j] & ~MSB;
}
C++
복사
so_long 과제 여담
frame을 0부터 59까지 반복하도록 짜야했는데,
// 1
frame = frame % 60;
// 2
++frame;
if (frame >= 60)
frame = 0;
C++
복사
위와 같이 두 방식이 있는데, 아래가 더 빠르다.
%는 대충 26클럭 정도 걸리는데,
if도 분기문이라 만만치않게 느리지만 60이 될 때만 분기하기 때문에 분기예측률이 높아서 아래가 더 낫다.