BFS 미로 길찾기

미로를 그래프로 해석하기

매핑 규칙

• 정점(Vertex) = 좌표 (y, x) 한 칸
• 간선(Edge) = 상/하/좌/우로 이동 가능하면 연결
• 벽('#')은 정점으로 보지 않거나, 정점이더라도 이동 불가 상태로 취급

즉, 미로는 "격자형 그래프"이며 BFS를 그대로 적용할 수 있습니다.

왜 BFS가 맞는가?

• 격자에서 한 번 이동 비용을 모두 1로 보면 비가중치 그래프입니다.
• BFS는 거리(이동 횟수)가 작은 칸부터 확장하므로, 목적지에 처음 도달한 경로가 최단 경로입니다.

보조 배열 역할

배열	의미	초기값
discovered[y][x]	큐에 넣었는지(중복 방문 방지)	false
dist[y][x]	시작점에서 거리(칸 수)	-1
parent[y][x]	어디서 왔는지(경로 복원용)	(-1,-1)

---

BFS 미로 템플릿 (실전형)

코드

struct Pos {
    int y, x;
    bool operator==(const Pos& other) const {
        return y == other.y && x == other.x;
    }
};

bool FindPathBfs(const vector<string>& board, Pos start, Pos dest, vector<Pos>& outPath) {
    int n = static_cast<int>(board.size());
    int m = static_cast<int>(board[0].size());

    auto InRange = [&](Pos p) {
        return (0 <= p.y && p.y < n && 0 <= p.x && p.x < m);
    };
    auto CanGo = [&](Pos p) {
        return InRange(p) && board[p.y][p.x] != '#';
    };

    if (!CanGo(start) || !CanGo(dest)) return false;

    vector<vector<bool>> discovered(n, vector<bool>(m, false));
    vector<vector<int>> dist(n, vector<int>(m, -1));
    vector<vector<Pos>> parent(n, vector<Pos>(m, Pos{-1, -1}));
    queue<Pos> q;

    static const int dy[4] = {-1, 0, 1, 0};
    static const int dx[4] = {0, 1, 0, -1};

    q.push(start);
    discovered[start.y][start.x] = true;
    dist[start.y][start.x] = 0;
    parent[start.y][start.x] = start;

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

        if (here == dest) break; // 목적지 도달 시 조기 종료 가능

        for (int dir = 0; dir < 4; dir++) {
            Pos next{here.y + dy[dir], here.x + dx[dir]};
            if (!CanGo(next)) continue;
            if (discovered[next.y][next.x]) continue;

            q.push(next);
            discovered[next.y][next.x] = true; // push 시점에 true
            dist[next.y][next.x] = dist[here.y][here.x] + 1;
            parent[next.y][next.x] = here;
        }
    }

    if (!discovered[dest.y][dest.x]) return false; // 도달 불가

    outPath.clear();
    for (Pos cur = dest;; cur = parent[cur.y][cur.x]) {
        outPath.push_back(cur);
        if (cur == start) break;
    }
    reverse(outPath.begin(), outPath.end());
    return true;
}

구현 포인트

• discovered는 큐에 넣을 때 켭니다(중복 삽입 방지).
• parent를 기록해두면 목적지에서 시작점으로 역추적이 가능합니다.
• start 또는 dest가 벽/범위를 벗어나면 즉시 실패 처리합니다.

---

동작 흐름 요약 (암기용)

1. 시작점 검증 (CanGo(start), CanGo(dest))
2. 큐 초기화 + 시작점 push + discovered/dist/parent 초기화
3. 큐 루프: pop -> 4방향 확장 -> 미발견 칸 push
4. 목적지 도달 여부 확인
5. parent 역추적 + reverse로 정방향 경로 생성

---

복잡도 (격자 N x M)

• 시간 복잡도: O(N*M)
  • 각 칸은 최대 1번 큐에 들어감
  • 각 칸에서 4방향 상수 탐색
• 공간 복잡도: O(N*M)
  • discovered, dist, parent, queue

---

자주 하는 실수 + 디버깅 체크

실수	증상	해결
discovered를 pop 시점에 true	큐에 중복 데이터 급증	push 시점에 true
parent 초기화 누락	역추적 중 무한 루프/깨진 경로	(-1,-1) 또는 자기 자신으로 초기화
도달 불가 체크 없음	경로 복원 중 인덱스 오류	if (!discovered[dest]) return false;
좌표 축 혼동 (x,y)	벽을 통과하거나 범위 오류	board[y][x] 규칙 고정
시작/도착이 벽인 경우 미처리	즉시 오답	시작 전에 CanGo 검사

---

BFS 미로의 한계 (다음 파트 연결)

• 최단 이동 횟수는 보장하지만, 가중치 지형(늪/고속도로 등)은 반영하지 못합니다.
• 목적지 방향 정보를 직접 쓰지 않아 큰 맵에서는 불필요한 확장이 많을 수 있습니다.
• 그래서 다음 파트에서 다익스트라(가중치), A*(목적지 유도)를 학습합니다.

---