키워드

• 탐색 방법 비교

이번 프로젝트는 그리드 바닥으로 작업하는 것들이 많다.
작업 중 하나는 특정한 타일의 주변의 n 칸의 범위의 타일들을 표시하는 것이다.

코딩테스트에서 봤던 문제들을 게임 작업에 직접 반영하는 작업이다.

탐색 방법

목표한 범위까지를 최대 깊이로 상정하고 이에 도달하는 방법을 DFS, BFS 둘 중 하나에서 골라야했다.

DFS를 사용한 이유

• BFS, DFS 둘다 시간 복잡도에서 큰 차이가 없었기에 처음 작업을 할 땐, 재귀방식의 DFS를 사용했다.
• 사실 이때 이렇게 구현한 가장 큰 이유는 재귀 방식으로 작성해서 코드를 간단하게 관리할 수 있을 것이라 생각했다.

변경한 이유

DFS를 쓸 때 안일했던 점은 최대 깊이가 얼마까지일지 몰랐다는 것이다.

• 재귀 방식의 특성상 무한히 많은 셀을 탐색할 수가 없다는 단점이 있다.
  • 콜 스택이 일정 범위(작동 환경에 따라 다른)에 도달하면 스택 오버플로우가 뜰 수 있다.
  • 문제는 직접 프로젝트에 적용했는데, 깊이가 대략 13~15 스택 쯤에서 오버플로우가 뜨기도 했다.

BFS로 변경

이 문제를 해결하는 방식은 스택 오버플로우가 일어나지 않도록 구조를 바꾸면 됐다.
스택 오버플로우가 일어나는 이유가 재귀 방식 때문이므로 이 부분을 바꾸어서 구현했다.

DFS를 스택 자료형을 이용해서 구현한다는 선택지도 있었지만 다양한 방식으로 구현을 해보고자 BFS로도 작성을 해보았다.

// bfs 방식으로 변경
    void FloodFill(Vector2 coord, int maxDepth, Func<int, int, int> calcCostOper, Action<Vector2> onAdded = null)
    {
        Queue<Vector2> queue = new Queue<Vector2>();
        Dictionary<Vector2, int > visited = new Dictionary<Vector2, int>();
        Action<Vector2, int> addAction = (point, depth) =>
        {
            visited.Add(point, depth);
            queue.Enqueue(point);
            onAdded?.Invoke(point);
        };
        
        addAction.Invoke(coord, 0);

        while (queue.Count > 0)
        {
            Vector2 curCoord = queue.Dequeue();

            for (int i = 0; i < fourDirection.GetLength(1); i++)
            {
                Vector2 newCoord = new Vector2(curCoord.x + fourDirection[0, i], curCoord.y + fourDirection[1, i]);
                if(!maps.ContainsKey(newCoord)) 
                    continue;
                
                // 비용 적용
                int depth = calcCostOper.Invoke(visited[curCoord], maps[newCoord].Cost);
                if (depth <= -1 || depth >= maxDepth + 1) 
                    continue;

                if (!visited.ContainsKey(newCoord)) //새 좌표 추가
                    addAction.Invoke(newCoord, depth);
                else if (visited[newCoord] > depth) // 기존보다 나은 경로로 갱신
                    visited[newCoord] = depth;
            }
        }
    }

#내일배움캠프 #스파르타내일배움캠프 #스파르타내일배움캠프TIL