Search
Duplicate
🥕

so_long 경로 유효성 간단하게 판단하기

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
과제
Scrap
태그
9 more properties
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이 될 때만 분기하기 때문에 분기예측률이 높아서 아래가 더 낫다.