baekjoon 2178:미로탐색

baekjoon 2178 미로탐색

2178번 미로탐색

접근

정해진 위치에서 최단거리 탐색이니까 bfs이다.

코드

#include <iostream> //iostream이 string 포함해서 string 헤더 따로 필요 없더라
#include <vector>
#include <queue>

using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n, m;
  cin >> n >> m;
  vector<vector<int>> v(n, vector<int>(m));
  vector<vector<bool>> visited(n, vector<bool>(m, false));
  vector<vector<int>> dist(n, vector<int>(m));
  for(int i = 0; i < n; i++){
    string s; cin >> s;
    for(int j = 0; j < m; j++){
      v[i][j] = s[j] - '0';
    }
  }
  queue<pair<int, int>> q;
  q.push({0, 0});
  visited[0][0] = true;
  dist[0][0] = 1;
  while(!q.empty()){
    pair<int, int> curr = q.front();
    q.pop();
    if(curr.first - 1 >= 0 && v[curr.first - 1][curr.second] == 1 && !visited[curr.first - 1][curr.second]){
      q.push({curr.first - 1, curr.second});
      visited[curr.first - 1][curr.second] = true;
      dist[curr.first - 1][curr.second] = dist[curr.first][curr.second] + 1;
    }
    if(curr.second - 1 >= 0 && v[curr.first][curr.second - 1] == 1 && !visited[curr.first][curr.second - 1]){
      q.push({curr.first, curr.second - 1});
      visited[curr.first][curr.second - 1] = true;
      dist[curr.first][curr.second - 1] = dist[curr.first][curr.second] + 1;
    }
    if(curr.first + 1 < v.size() && v[curr.first + 1][curr.second] == 1 && !visited[curr.first + 1][curr.second]){
      q.push({curr.first + 1, curr.second});
      visited[curr.first + 1][curr.second] = true;
      dist[curr.first + 1][curr.second] = dist[curr.first][curr.second] + 1;
    }
    if(curr.second + 1 < v[0].size() && v[curr.first][curr.second + 1] == 1 && !visited[curr.first][curr.second + 1]){
      q.push({curr.first, curr.second + 1});
      visited[curr.first][curr.second + 1] = true;
      dist[curr.first][curr.second + 1] = dist[curr.first][curr.second] + 1;
    }
  }
  cout << dist[n-1][m-1] << "\n";
  return 0;
}

배운 점

iostream 이 string 헤더 포함한다.