BFS를 이용한 길찾기 구현

💡 BFS 기반의 길찾기 흐름

• BFS는 시작점에서 인접한 정점들을 모두 방문하고, 그 다음 단계로 넘어가서 또 인접 정점들을 방문하는 방식입니다.
• 이 구조 덕분에 처음 도달한 경로가 곧 최단 거리라는 보장이 생기고, 이를 통해 경로 추적도 가능하게 됩니다.

---

📌 핵심 코드 전체 흐름

void Player::Bfs()
{
    Pos pos = _pos;
    Pos dest = _board->GetExitPos();

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

    const int32 size = _board->GetSize();
    vector<vector<bool>> discovered(size, vector<bool>(size, false));
    map<Pos, Pos> parent;
    queue<Pos> q;

    q.push(pos);
    discovered[pos.y][pos.x] = true;
    parent[pos] = pos;

    while (!q.empty())
    {
        pos = q.front();
        q.pop();

        if (pos == dest)
            break;

        for (int32 dir = 0; dir < 4; dir++)
        {
            Pos nextPos = pos + front[dir];

            if (!CanGo(nextPos)) continue;
            if (discovered[nextPos.y][nextPos.x]) continue;

            q.push(nextPos);
            discovered[nextPos.y][nextPos.x] = true;
            parent[nextPos] = pos;
        }
    }

    _path.clear();
    pos = dest;

    while (true)
    {
        _path.push_back(pos);
        if (pos == parent[pos]) break;
        pos = parent[pos];
    }

    std::reverse(_path.begin(), _path.end());
}

---

📖 한 줄 한 줄 코드 분석

🎲 1. 시작점과 목적지 설정

Pos pos = _pos;
Pos dest = _board->GetExitPos();

• 현재 위치와 도착 지점을 Pos 타입으로 받아옵니다.
• Pos는 (x, y) 좌표를 나타내는 구조체로 추정됩니다.

---

🧭 2. 방향 배열

Pos front[4] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

• 상, 좌, 하, 우 네 방향을 미리 정의하여 반복문을 간결하게 만듭니다.

---

🗺️ 3. 초기화: 맵 정보, 큐, 부모 맵

vector<vector<bool>> discovered(size, vector<bool>(size, false));
map<Pos, Pos> parent;
queue<Pos> q;

• discovered: 방문 여부 체크 (중복 탐색 방지)
• parent: 경로 추적용. child → parent 구조
• q: BFS용 큐

q.push(pos);
discovered[pos.y][pos.x] = true;
parent[pos] = pos;

• 시작 위치를 큐에 삽입하고 방문 처리합니다.
• 시작점의 부모는 자기 자신으로 설정합니다.

---

🔁 4. BFS 탐색

while (!q.empty())
{
    pos = q.front();
    q.pop();

    if (pos == dest) break;

    for (int32 dir = 0; dir < 4; dir++)
    {
        Pos nextPos = pos + front[dir];

        if (!CanGo(nextPos)) continue;
        if (discovered[nextPos.y][nextPos.x]) continue;

        q.push(nextPos);
        discovered[nextPos.y][nextPos.x] = true;
        parent[nextPos] = pos;
    }
}

• 매 반복마다 큐에서 현재 위치를 꺼냅니다.
• 목적지에 도달했으면 탐색 종료.
• 4방향으로 이동 가능한지 확인 후, 조건을 만족하면 큐에 넣고 부모 기록.

🔒 CanGo(nextPos)는 이동 가능한 타일인지 체크하는 함수입니다. 벽이나 장애물이 있는 경우 false 반환.

---

🧵 5. 최단 경로 추적

_path.clear();
pos = dest;

while (true)
{
    _path.push_back(pos);

    if (pos == parent[pos])
        break;

    pos = parent[pos];
}

std::reverse(_path.begin(), _path.end());

• parent를 따라 목적지부터 시작점까지 거슬러 올라가며 경로를 _path에 저장.
• 뒤에서부터 저장되기 때문에 reverse()를 통해 정방향으로 정리.

---

⚠️ BFS의 한계와 단점

// 단점
// - 목적지 방향 고려 없이 그냥 가까운 칸부터 탐색
// - 대각선 이동 불가능

1. 목적지 방향 고려 X

   • BFS는 목적지에 대한 정보 없이 탐색하므로, 불필요한 경로까지 탐색할 수 있음.

2. 대각선 이동 미지원

   • front[4] 배열만 쓰면 상하좌우만 이동 가능.
   • 대각선도 탐색하려면 front[8] 형태로 변경 필요.

---