Subject
so long 과제에 추가된 조건들
그래프 순회와 DFS
구현
1. so long 과제에 추가된 조건들
so long 과제에서 다음과 같은 조건들이 추가되었다.
- The map must contain 1 exit, at least 1 collectible, and 1 starting position to
be valid.
- You have to check if there’s a valid path in the map.
이전과는 달리 탈출구 1개, 적어도 1개 이상의 수집품, 1개의 시작 위치라는 조건이 추가되었다. 또한 맵 안에 유효한 경로가 있는지를 확인해야 한다.
유효한 경로라는 말이 다소 애매하게 느껴졌지만, 처음 시작 위치(P)에서 모든 수집품(C)들을 수집하고, 탈출구(E)에 도달할 수 있는 경로가 존재할 때 맵 안에 유효한 경로가 있다고 생각했다.
2. 그래프 순회와 DFS
시작위치(P)부터 시작해서 벽으로 둘러싸인 영역에 있는 좌표들을 하나씩 방문하면서, 각 구성요소들을 확인하면 된다고 생각하였다. 즉, 그래프의 각 정점을 방문하는 그래프 순회 알고리즘을 활용한다면 맵의 유효성을 확인할 수 있다.
그래프 순회 알고리즘 : DFS, BFS
과제에서 맵의 유효성 검사를 할 때는 DFS와 BFS 모두 활용할 수 있었다. 다만, BFS를 활용하기 위해서는 최적화를 하기 위해서는 큐를 따로 구현해야 했다. 물론 배열의 삽입, 삭제로 큐의 동작과 유사하게 구현할 수도 있었지만 이 때 시간 복잡도가 O(N)으로 비효율적이라 생각했다. DFS의 스택을 이용한 구현도 최적화를 위해서는 스택을 따로 구현해야 했기에, 재귀구조를 이용한 DFS를 선택하였다.
3. 구현
플레이어의 시작 위치에서 선물들을 모두 수집하고, 탈출구로 빠져나가야 한다.
맵 안에 유효한 경로가 있는 조건은 다음과 같다.
1.
전체 ‘C’의 개수 = P가 속한 벽으로 막힌 구역에서 센 ‘C’의 개수
2.
1 = P가 속한 벽으로 막힌 구역에서 센 ‘E’의 개수
이를 확인하는 함수명을 has_path_valid라고 하였다.
1) 처음 작성한 코드
int dfs(int x, int y, t_info *player, char **visited)
{
if (x <= -1 || x >= player->width || y <= -1 || y >= player->height)
return (0);//이 조건은 벽으로 적절히 둘러싸여 있다는 가정 하에는 쓸 필요가 없다.
if ((player->map)[y][x] == '1')
return (0);//그래프를 순회하다가 벽에 도달하면 return을 해 아래의 코드를 실행시키지 못하게 함
if (visited[y][x] == '0')
{
visited[y][x] = '1';
if ((player->map)[y][x] == 'E')
(player->total_e_count)++;
if ((player->map)[y][x] == 'C')
(player->total_c_count)++;
dfs(x - 1, y, player, visited);//위,아래, 양옆으로 나아간다.
dfs(x, y - 1, player, visited);
dfs(x + 1, y, player, visited);
dfs(x, y + 1, player, visited);
return (1);
}
return (0);
}
C
복사
int has_valid_path(t_info *player, t_info *board)
{
char **visited;
visited = make_2dim_zero(board->height, board->width);
dfs(player->x, player->y, player, visited);
if (player->total_c_count != board->total_c_count)
return (0);//플레이어가 수집할 수 있는 수집품 개수가 전체 수집품 개수와 다르면 false
if (player->total_e_count != 1)
return (0);//탈출구 개수가 1이 아니면 false
return (1);
}
C
복사
여기서 메모리 누수를 해결하는 코드는 쓰지 않았다.
처음에는 has_valid_path라는 함수 내에서 dfs 함수를 호출하고, 구조체의 바뀐 정보(탈출구 개수, 수집품 개수)들을 확인하여 경로가 유효한지 확인하였다. 구조체에 너무 많은 변수들을 담아 놨다는 점과 dfs함수의 return 값이 함수 실행을 종료시킨다는 점 외에는 아무 의미가 없다는 점이 아쉬웠다.
실질적으로 함수에서 쓰이는 변수가 많았기 때문에, 그에 따라 일어나는 부수효과들도 통제하기 어렵다고 생각했다.
그래서 다음과 같은 목표를 세우고, 함수를 수정해보기로 했다.
1.
dfs 함수에 넣는 입력값을 최대한 줄여보자.
2.
return 값이 의미를 갖게끔 하자.
3.
새로운 이차원 배열을 만들어서 처리하기 보다, 기존 map에서 해결하자.
4.
함수의 기능을 하나만 담도록 하자.
2) 수정한 코드
int dfs(int x, int y, char **map, char find_char)
{
int count;
if (x <= -1 || x >= ft_strlen(map[0]) || y <= -1 || y >= get_height(map))
return (0);//이 조건은 벽으로 적절히 둘러싸여 있다는 가정 하에는 쓸 필요가 없다.
if (map[y][x] == '1')
return (0);
if (map[y][x] != 'V')//방문처리('V)한 노드가 아니라면
{
if (map[y][x] == find_char)
{
map[y][x] = 'V'; // 'V'로 노드를 방문처리를 하였다.
return (1);
}
map[y][x] = 'V';
count = 0;
count += dfs(x - 1, y, map, find_char);//위,아래, 양옆으로 나아간다.
count += dfs(x, y + 1, map, find_char);
count += dfs(x + 1, y, map, find_char);
count += dfs(x, y - 1, map, find_char);
return (count);
}
return (0);
}
C
복사
위의 코드와 비교하기 위해 ‘함수명’을 dfs라 썼지만, 함수의 기능을 더 설명하기 위해서는 get_count라는 함수명이 더 좋을 거 같다. get_height라는 함수는 map에서 세로 길이를 구하는 함수라고 보면 된다.
int has_valid_path(char **map, t_info *board)
{
char **map_temp_c;
map_temp_c = duplicate(map); //duplicate는 이차원 배열들의 값을 복사하는 함수
map_temp_e = duplicate(map);
int c_count = dfs(player_x, player_y, map_temp_c, 'C');
int e_count = dfs(player_x, player_y, map_temp_e, 'E');
if (c_count != board->total_c_count)
return (0);//플레이어가 수집할 수 있는 수집품 개수가 전체 수집품 개수와 다르면 false
if (e_count != 1)
return (0);//탈출구 개수가 1이 아니면 false
return (1);
}
C
복사
여기서 메모리 누수를 해결하는 코드는 쓰지 않았다.
위의 목표를 반영하여 코드를 수정했다. 기존과 다르게 visited라는 이차원 배열을 따로 만들기 보다 기존 map을 복사한 배열을 입력값으로 넣어, 함수에 들어가는 변수를 줄이고, dfs함수가 찾아야 하는 문자의 개수를 세는 기능만 갖게 했다. 변수로 찾아야 하는 문자도 입력값으로 추가해서 함수의 사용범위를 넓히고자 했다.
3) 느낀 점
기존에 파이썬으로 알고리즘 문제를 풀 때는 전역변수도 썼던 거 같은데, 이번 과제에서 DFS알고리즘을 구현할 때는, 전역변수를 쓰지 못하는 조건이 있어서 까다롭게 느껴졌다. 그리고 이번에 코드를 다시 수정하면서, 내 머릿속에서 생각한 거랑, 실제로 작동하는 거랑 다를 때가 많다는 걸 다시 한번 깨닫게 되었다.그래프에서 특정한 조건을 만족하는 트리 구조도 공부해 봐야겠다.
참고자료
