인프런 커뮤니티 질문&답변

항상 좋은 강의 잘 듣고 있습니다.

다름이 아니라 Astar 알고리즘에 대해서 복습하던 중 궁금한 점이 생겨 질문드리게 되었습니다.

 

Astar 알고리즘에서 open 배열과 우선순위 큐를 사용하셨는데, 우선순위 큐를 사용하면 open 배열 없이도 구현할 수 있지 않나요?

 

조금 코드를 변형시켜 open 배열 없이

다음과 같이 구현해 보았습니다.

open배열을 사용하는것에 대한 장점이 따로 있을까요?

 

        void AStar() 
        {
            // U L D R UL DL DR UR
            int[] deltaY = new int[] { -1, 0, 1, 0, -1, 1, 1, -1 };
            int[] deltaX = new int[] { 0, -1, 0, 1, -1, -1, 1, 1 };
            int[] cost = new int[] { 10, 10, 10, 10, 14, 14, 14, 14 };
           
            bool[,] closed = new bool[_board.Size,_board.Size]; 

            // 삭제
            //int[,] open = new int[_board.Size, _board.Size]; // OpenList
            //for (int y = 0; y < _board.Size; y++)
            //    for (int x = 0; x < _board.Size; x++)
            //       open[y, x] = Int32.MaxValue;

            Pos[,] parent = new Pos[_board.Size, _board.Size];

            PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
            
            //open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX));

            //PQNode에 parent 추가
            pq.Push(new PQNode() { F = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)), G = 0, Y = PosY, X = PosX, parent= new Pos(PosY, PosX)});


            while (pq.Count > 0)
            {

                PQNode node = pq.Pop();
                if (closed[node.Y, node.X])
                    continue;

                closed[node.Y, node.X] = true;
                //추가
                parent[node.Y, node.X] = node.parent;

                if (node.Y == _board.DestY && node.X == _board.DestX)
                    break;
                for (int i = 0; i < deltaY.Length; i++)
                {
                    int nextY = node.Y + deltaY[i];
                    int nextX = node.X + deltaX[i];

                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
                        continue;

                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                        continue;

                    if (closed[nextY, nextX])
                        continue;

                    int g = node.G + cost[i];
                    int h = 10 * (Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX));

                    //삭제
                    //if (open[nextY, nextX] < g + h)
                    //    continue;

                    //삭제
                    //open[nextY, nextX] = g + h; 
                    pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX, parent = new Pos(node.Y, node.X) }); //parent 추가
                    
                }
            }
            CalcPathFromParent(parent);
        }

읽어주셔서 감사합니다.