[BOJ/2178번미로탐색] c++ / BFS

문제

첫번째 칸에서 마지막 칸까지 가는 최단 경로의 길이를 구하는 문제

 

문제해결

bfs를 통해 1이 적힌 칸의 개수를 찾는 것은 쉬웠는데, 최단 경로를 어떤식으로 구해야하는지 감이 안왔음

다른 분이 작성하신 코드를 보고 '아!!!!' 했음

 

일단, 각 칸에 첫번째 칸부터 해당위치의 칸까지의 길이를 저장할 cnt배열을 만들어야함 (-첫번째 칸은 길이가 1 임)

-(0, 0) 칸의 상하좌우에 길이 있는지 확인

-(1, 0)에 길이 있다면 방문표시 & cnt 배열 (1, 0)에 cnt[0][0]값 + 1 을 넣어줌 

-(1, 0)에 길이 있다면 방문표시 & cnt 배열 (0, 1)에 cnt[0][0]값 + 1 을 넣어줌 

-마지막 칸에 도착하면 bfs 종료 ( 난 Q가 빌때까지 했음 )

-마지막 칸의 cnt배열 값이 최단 경로의 길이가 됨

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define X first
#define Y second
string board[102];
bool vis[102][102];
int cnt[102][102];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m, ck = 0;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for ( int i = 0; i < n; i++ )
        cin >> board[i]; // 배열 입력
    
    queue<pair<int, int>> Q;
    vis[0][0] = 1; // 첫번째 칸 방문표시
    cnt[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.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;
            if ( vis[nx][ny] || board[nx][ny] != '1' ) continue;
            
            vis[nx][ny] = 1;
            cnt[nx][ny] = cnt[cur.X][cur.Y]+1; // 핵심 부분 !!!!
            Q.push({nx, ny});
        }
    }
            
    cout << cnt[n-1][m-1];

}