[백준/2178][C++] 미로 탐색

거리계산과 방문 체크 배열을 따로 만들지 않고, vis배열을 우선 -1로 초기화해서 한번도 방문하지 않은 노드를 -1로 나타낼 수 있도록 하였다.  방문을 한 경우 바로 전 노드의 거리에 +1을 해주었다. 그렇게해서 시작점부터 특정 정점까지 모든 위치의 거리를 구할 수 있었다.

 

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

int n,m;
string board[102];
int vis[102][102];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>board[i];
    }//입력받기
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            vis[i][j]=-1;
        }
    }// 전부 -1로 초기화 한 뒤, 거리 계산 시작 
    //-1이면 방문 안한 노드
    queue<pair<int,int>> q;
    q.push({0,0});
    vis[0][0]=0;
    while(!q.empty()){
        auto 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||ny<0||nx>=n||ny>=m) continue;
            if(board[nx][ny]=='0'||vis[nx][ny]>=0) continue;            
            vis[nx][ny]=vis[cur.first][cur.second]+1;
            q.push({nx,ny});
        }
    }
    cout<<vis[n-1][m-1]+1;

}