미로 탐색 — BFS로 최단 거리 (BOJ 2178)

아이디어

• 미로는 가중치가 없는 그래프 → BFS로 최단 칸 수 계산.
• vis[x][y]에 방문 여부 대신 **시작점부터의 거리(칸 수)**를 저장.
• 시작 (0,0)을 1로 두고 사방 탐색하며 vis = 이전 + 1.

알고리즘

1. 입력을 문자열로 받아 adj[i][j] = temp[j] - '0'로 변환.

2. 큐에 (0,0)을 넣고 vis[0][0] = 1.

3. 큐가 빌 때까지:

   • 현재에서 4방향으로 이동
   • 범위 밖/이미 방문/벽(0)이면 건너뛰기
   • 조건 통과 시 vis[nx][ny] = vis[cur] + 1로 갱신하고 큐 삽입

4. 답은 vis[n-1][m-1].

복잡도

• 시간: O(n·m)
• 공간: O(n·m)

코드 (원문)

#include <bits/stdc++.h>
using namespace std;

int adj[502][502];
int vis[502][502];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    string temp;
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        for (int j = 0; j < temp.size(); j++) {
            adj[i][j] = temp[j] - '0';
        }
    }

    queue<pair<int, int>> q;
    vis[0][0] = 1;
    q.push({0, 0});
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[nx][ny] || adj[nx][ny] != 1) continue;
            vis[nx][ny] = vis[cur.first][cur.second] + 1;
            q.push({nx, ny});
        }
    }
    cout << vis[n - 1][m - 1];
    return 0;
}

메모

• 시작점이 막혀 있지 않다는 전제(문제 조건).
• vis가 0이면 미방문, 양수면 거리로 처리되어 로직이 깔끔.