[개발일지] BFS를 활용해서 만든 최단 경로 탐색 툴

그동안 백준만 풀다가 게임 개발 공부나 CS에 대한 개념적인 부분에 있어서 많은 부족함이 있다는걸 깨닫고 당분관 백준을 쉬면서 기본적인 개념들을 차차 공부해 나갔다.

간단히 if문부터 다시 복습해보기도 하고..Direct9으로 간단한 쉐이더를 만들어서 적용해보기도 하였다.

그리고 어제 인터넷 강좌를 보면서 Graph라는 거와 DFS, BFS라는 기법?을 알게되었는데, 이중 BFS를 활용하면 최단거리를 구할 수 있다는 거다.

 

평소에 jinho Lee분의 영상을 자주 챙겨보고 있는데, 그동안 동경하면서 봐았지만 실제로 직접 만들어볼 엄두가 나질 않았었는데 이번 기회에 한번 간단하게 만들어보았다.

 

(182) DevLog TurnSystem Test (게임 개발일지) - YouTube

 

그 결과로 아래 사진처럼 시작지점과 끝지점을 입력하고 서치를 하면 최단 경로만 표시해주는 툴을 만들었다.

(182) 최단경로 탐색 - YouTube

 

사실 말이 최단 경로 탐색이지 실질적으로 거리(가중치) 까지 고려해서 만든게 아니므로 노드간 최소한의 진입 경로만 알려줄 뿐이지 거리까지는 고려하지 않았다.

사실 여기서 거리까지 추가해서 제작을 한다면 그게 다익스트라(Dijkstra)가 되는것 같다.

 

오랜만에 알고리즘이나 자료구조를 활용해서 이런것들을 만들어보니깐 느낀점이 있었는데 알고리즘이나 자료구조를 통해서 다양한 상황에 대하여 접근할 수 있는 방향성을 제공해줘서 좋은 것 같다.

 

만약 내가 그래프와 BFS를 알고있지 않았던 때라면 이런걸 만들어보라고 해도 만들지 못했을 것이다(만약 했다고 해도 하드코딩으로 버그만 남긴 채 끝났을 것 같다..).

 

이래서 알고리즘이나 자료구조, 컴퓨터 과학에 대한 기본적인 개념이 필요한 것 같다...