[알고리즘] BFS 최단거리 길찾기

BFS의 가장 가까운 노드부터 순회하는 특징을 활용하여 최단거리 길찾기 기능을 구현할 수 있다.

가장 가까운 노드부터 순회한다는 것은 어떠한 노드가 발견된 순간의 경로가 그 노드에 도착하는 데 최단거리 경로라는 것을 보장하기 때문이다.

 

로직

1. BFS탐색을 한다.
2. 탐색을 진행하며 탐색된 노드가 어떠한 노드로부터 발견되었는지를 부모 노드로서 저장한다.
3. 탐색이 끝난 후 도착점에서 부모 노드를 타고 올라가며 시작점에 도착할 때 까지의 부모 노드들을 저장한다. 
4. 저장한 부모 노드들의 순서를 역전시킨다.

 

구현

미로에서의 길찾기를 구현하였다.

노드는 Pos라는 클래스를 정의하여 나타내었다.

 

public class Pos
{
    public Pos(int x, int y) { X = x; Y = y; }
    public int X;
    public int Y;
}

void PathFindingByBFS()
{
    int[] deltaX = { -1, 0, 1, 0 };
    int[] deltaY = { 0, -1, 0, 1 };

    bool[,] found = new bool[board.Size, board.Size];
    Pos[,] parent = new Pos[board.Size, board.Size];
    Queue<Pos> q = new Queue<Pos>();
    List<Pos> points = new List<Pos>();
    
    q.Enqueue(new Pos(PosX, PosY));
    found[PosY, PosX] = true;
    parent[PosY, PosX] = new Pos(PosX, PosY);

	// BFS
    while(q.Count > 0)
    {
        Pos pos = q.Dequeue();

        for(int i = 0; i < 4; i++)
        {
            Pos next = new Pos(pos.X + deltaX[i], pos.Y + deltaY[i]);

            if (next.X < 0 || next.X >= board.Size || next.Y < 0 || next.Y >= board.Size)
                continue;
            if (board.Tile[next.Y, next.X] == Board.TileType.Wall)
                continue;
            if (found[next.Y, next.X] == true)
                continue;

            q.Enqueue(next);
            found[next.Y, next.X] = true;
            parent[next.Y, next.X] = pos; // 어떤 노드에서 찾았는지 저장
        }
    }

    int x = board.DestX;
    int y = board.DestY;
    // 자기 자신과 같은 경우 == 시작점
    // 도착점에서 시작하여 시작점에 도달할 때 까지 부모 노드 저장
    while (parent[y, x].Y != y || parent[y, x].X != x)
    {
        points.Add(new Pos(x, y));
        Pos pos = parent[y, x];
        y = pos.Y;
        x = pos.X;
    }
    points.Add((new Pos(PosX, PosY)));
    // 순서 역전
    points.Reverse();
}