Subject

1. so long 과제에 추가된 조건들

so long 과제에서 다음과 같은 조건들이 추가되었다.

이전과는 달리 탈출구 1개, 적어도 1개 이상의 수집품, 1개의 시작 위치라는 조건이 추가되었다. 또한 맵 안에 유효한 경로가 있는지를 확인해야 한다.

유효한 경로라는 말이 다소 애매하게 느껴졌지만, 처음 시작 위치(P)에서 모든 수집품(C)들을 수집하고, 탈출구(E)에 도달할 수 있는 경로가 존재할 때 맵 안에 유효한 경로가 있다고 생각했다.

2. 그래프 순회와 DFS

시작위치(P)부터 시작해서 벽으로 둘러싸인 영역에 있는 좌표들을 하나씩 방문하면서, 각 구성요소들을 확인하면 된다고 생각하였다. 즉, 그래프의 각 정점을 방문하는 그래프 순회 알고리즘을 활용한다면 맵의 유효성을 확인할 수 있다.

그래프 순회 알고리즘 : DFS, BFS

https://velog.velcdn.com/images%2Fleobit%2Fpost%2Fd866ead5-4b59-4bf2-ac47-66a4371412da%2FDFS-BFS-comparison.gif

과제에서 맵의 유효성 검사를 할 때는 DFS와 BFS 모두 활용할 수 있었다. 다만, BFS를 활용하기 위해서는 최적화를 하기 위해서는 큐를 따로 구현해야 했다. 물론 배열의 삽입, 삭제로 큐의 동작과 유사하게 구현할 수도 있었지만 이 때 시간 복잡도가 O(N)으로 비효율적이라 생각했다. DFS의 스택을 이용한 구현도 최적화를 위해서는 스택을 따로 구현해야 했기에, 재귀구조를 이용한 DFS를 선택하였다.

3. 구현