baekjoon 14940:쉬운 최단거리

baekjoon 14940 쉬운 최단거리

14940번 쉬운 최단거리

접근

bfs 거꾸로 접근하면 된다.
조금 변형해서 상하좌우로 탐색하도록 했다.

코드

#include <iostream>
#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>> graph(n, vector<int>(m, 0));
  vector<vector<bool>> visited(n, vector<bool>(m, false));
  vector<vector<int>> dist(n, vector<int>(m, -1));
  int s1, s2;
  queue<pair<int, int>> q;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      int temp;
      cin >> temp;
      if(temp == 2){
        s1 = i;
        s2 = j;
      }
      else if(temp == 0){
        dist[i][j] = 0;
      }
      graph[i][j] = temp;
    }
  }
  visited[s1][s2] = true;
  dist[s1][s2] = 0;
  q.push({s1, s2});
  while(!q.empty()){
    pair<int, int> curr = q.front();
    q.pop();
    if(curr.first-1 >= 0 && graph[curr.first-1][curr.second] == 1 && !visited[curr.first-1][curr.second]){
      visited[curr.first-1][curr.second] = true;
      dist[curr.first-1][curr.second] = dist[curr.first][curr.second] + 1;
      q.push({curr.first-1, curr.second});
    }
    if(curr.first+1 < n && graph[curr.first+1][curr.second] == 1 && !visited[curr.first+1][curr.second]){
      visited[curr.first+1][curr.second] = true;
      dist[curr.first+1][curr.second] = dist[curr.first][curr.second] + 1;
      q.push({curr.first+1, curr.second});
    }
    if(curr.second-1 >= 0 && graph[curr.first][curr.second-1] == 1 && !visited[curr.first][curr.second-1]){
      visited[curr.first][curr.second-1] = true;
      dist[curr.first][curr.second-1] = dist[curr.first][curr.second] + 1;
      q.push({curr.first, curr.second-1});
    }
    if(curr.second+1 < m && graph[curr.first][curr.second+1] == 1 && !visited[curr.first][curr.second+1]){
      visited[curr.first][curr.second+1] = true;
      dist[curr.first][curr.second+1] = dist[curr.first][curr.second] + 1;
      q.push({curr.first, curr.second+1});
    }
    
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cout << dist[i][j] << " ";
    }
    cout << "\n";
  }
  
  
  return 0;
}

배운 점

bfs 응용방법을 배운 것 같다.