중점:
1. bfs 알고리즘 사용
2. N, M 좌표까지 vis 값 +1
정답 코드:
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[105];
int vis[105][105];
int n, m;
int dx[] = {1, 0 , -1, 0};
int dy[] = {0, 1, 0, -1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m; //n, m값 입력 받음.
for (int i = 0; i < n; i++){ //board 값 입력 받음.
cin >> board[i];
}
vis[0][0] = 1;
queue<pair<int, int> > Q;
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] = vis[cur.X][cur.Y] + 1;
Q.push({nx, ny});
}
}
cout << vis[n - 1][m - 1];
}