BFS 기반 길찾기

1. CalculatePath_BFS 개요

CalculatePath_BFS 함수는 미로와 같은 2차원 맵에서 BFS(너비 우선 탐색) 알고리즘을 사용하여 최단 경로를 찾는 메서드입니다. BFS는 시작점에서 가까운 정점부터 차례대로 탐색하므로 최단 경로를 보장합니다. 코드의 각 부분을 한 줄 한 줄 자세히 분석합니다.

---

2. 주요 데이터 구조

Pos 구조체

• Pos는 좌표를 나타내는 데이터 구조입니다. 좌표 (x, y)를 포함하며, 연산자 오버로딩을 통해 덧셈 연산이 가능한 것으로 보입니다.

---

3. 코드 분석

그래프 정보 초기화

Pos pos = _pos;
Pos dest = _board->GetExitPos(); // 목적지
_path.clear();
_path.push_back(pos);

• pos: 시작 좌표를 설정합니다.
• dest: 보드에서 목적지 좌표를 가져옵니다.
• _path: BFS 탐색 과정에서 경로를 저장할 벡터로 초기화합니다.

---

맵 크기 및 방문 여부 초기화

const int32 size = _board->GetSize();
vector<vector<bool>> discovered(size, vector<bool>(size, false));

• size: 맵의 크기를 가져옵니다.
• discovered: 2차원 벡터로 방문 여부를 나타냅니다. 초기값은 false입니다.

---

방향 정보 정의

Pos front[4] =
{
    Pos(-1, 0), // UP
    Pos(0, -1), // LEFT
    Pos(1, 0),  // DOWN
    Pos(0, 1),  // RIGHT
};

• front: 4방향(위, 왼쪽, 아래, 오른쪽)을 나타내는 배열입니다.
• 이 배열을 사용하여 현재 좌표에서 탐색 가능한 방향을 계산합니다.

---

부모 노드 정보 초기화

vector<vector<Pos>> parent(size, vector<Pos>(size, Pos(-1, -1)));
parent[pos.y][pos.x] = pos;

• parent: 경로를 역추적하기 위한 2차원 벡터입니다.
• 각 좌표 (y, x)에 대해 BFS 탐색 중에 어떤 노드에서 왔는지 저장합니다.
• 초기값은 Pos(-1, -1)로 설정합니다.

---

BFS 큐 초기화

queue<Pos> q;
q.push(pos);
discovered[pos.y][pos.x] = true;

• queue<Pos>: BFS는 큐를 사용하여 탐색합니다.
• 시작 좌표를 큐에 추가하고, 해당 좌표를 discovered로 표시합니다.

---

BFS 탐색 루프

while (q.empty() == false)
{
    pos = q.front();
    q.pop();
    if (pos == dest)
    {
        break; // 목적지에 도달하면 종료
    }

• 큐 처리:
  • q.front(): 큐의 첫 번째 좌표를 가져옵니다.
  • q.pop(): 큐에서 첫 번째 좌표를 제거합니다.
• 목적지 확인:
  • 현재 좌표가 dest와 같으면 탐색을 종료합니다.

---

인접한 좌표 탐색

    for (int32 dir = 0; dir < DIR_COUNT; dir++)
    {
        Pos nextPos = pos + front[dir]; // 다음 좌표 계산
        if (CanGo(nextPos) == false) // 유효성 검사
        {
            continue;
        }
        if (discovered[nextPos.y][nextPos.x]) // 이미 방문 여부 확인
        {
            continue;
        }
        q.push(nextPos); // 큐에 추가
        discovered[nextPos.y][nextPos.x] = true; // 방문 표시
        parent[nextPos.y][nextPos.x] = pos; // 부모 설정
    }
}

1. for 루프:
   • front 배열을 사용해 4방향으로 탐색합니다.
2. 유효성 검사:
   • CanGo(nextPos): 해당 좌표가 갈 수 있는 좌표인지 확인합니다.
   • discovered[nextPos.y][nextPos.x]: 이미 방문한 좌표는 제외합니다.
3. 큐 처리:
   • 유효한 좌표를 큐에 추가합니다.
   • parent에 부모 정보를 저장합니다.

---

경로 생성

_path.clear();
pos = dest;
while (true)
{
    _path.push_back(pos); // 현재 좌표를 경로에 추가
    if (pos == parent[pos.y][pos.x])
    {
        break; // 시작점 도달
    }
    pos = parent[pos.y][pos.x]; // 부모를 따라 역추적
}

1. _path: 최단 경로를 저장하는 벡터로 초기화합니다.
2. 경로 역추적:
   • parent 정보를 따라 시작점까지 역추적하며 좌표를 _path에 추가합니다.

---

경로 뒤집기

vector<Pos> temp(_path.size());
for (int i = 0; i < _path.size(); i++)
{
    temp[i] = _path[_path.size() - 1 - i];
}
_path = temp;

// std::reverse 활용
// std::reverse(_path.begin(), _path.end());

• _path는 역추적 과정에서 역순으로 저장되므로 뒤집어야 올바른 경로가 됩니다.
• std::reverse: STL 함수를 사용하면 간단히 뒤집을 수 있습니다.

---

4. 코드의 한계

• BFS는 최단 경로를 보장하지만 탐색 효율이 낮습니다.
  • 모든 노드를 탐색하므로 불필요한 연산이 많습니다.
  • 최적화를 위해 A* 알고리즘과 같은 휴리스틱 탐색을 사용할 수 있습니다.

---

5. 보완점

1. 목적지 도달 여부 최적화:
   • BFS는 모든 노드를 탐색하므로 탐색 종료 조건을 추가하여 탐색을 조기에 종료할 수 있습니다.
2. 코드 간결화:
   • std::reverse를 사용해 경로 뒤집기를 간단히 처리합니다.

---