baekjoon 2206:벽 부수고 이동하기

baekjoon 2206 벽 부수고 이동하기

2206번 벽 부수고 이동하기

접근

a~>b~>c
이런 경로가 있다고 하자.
일반적인 bfs의 경우 k길이 search를 끝내고 k+1 search를 시작하니까
a에서b에 처음 도착만 하면 그게 최단 길이다. k-1까지는 도착 못했다는 거니까
이번 문제에서는 최대 한번 까지 벽을 뚫을 수 있다는 것이 차이점이다.
지금 만난 벽을 뚫지 않고 돌아가는 길을 고려하는게 나을 수도 있지 않냐
맞다. 물론 마지막에는 먼저 도착하면 장땡이지만 중간에는 그렇지 않을 수도 있다.
그래서 결국 둘다를 따져봐야하는 것이다.
일단 지금 당장 경로에서 벽을 만났다면 뚫어야한다. 벽을 뚫지않으면 포기하는거나 마찬가지다. 그 벽만 뚫으면 될 수도 있는데
포기하는 것은 바보같은 행동이다. 그리고 사방으로 탐색중이니 벽을 만나지 않고 돌아가는 경로도 동시에 탐색되고 있다.
그리고 이차원 matrix만 쓰면 벽을 뚫고 가는거와 벽을 안 뚫고 돌아가는거랑을 동시에 고려할 수 있다.
둘 중 뭐가 좋을지는 마지막에와서 따져야하는데 중간b같은 node에 둘이 도착했을 때 벽을 뚫고 온 것이 먼저 도착해서
벽을 뚫지 않고 온 경로가 무시될 수 있다. 나중에 b~>c경로에서 모든 경로가 최소 벽을 1번은 뚫고 가야할 때,
경로가 없다고 나오는 경우가 발생할 수 있다. 그래서 3차원 matrix로 벽을 뚫지 않은 경로도 끝까지 들고가야한다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int dy[2] = {-1, 1};
int dx[2] = {-1, 1};
bool checkRange(int y, int x, int n, int m);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> map(n, vector<int>(m));
  vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(2, -1))); //-1이면 !visited인거다 
  queue<tuple<int, int, bool>> q; //3차원이니 tuple
  for(int i = 0; i < n; i++){
    string s; cin >> s;
    for(int j = 0; j < m; j++){
      map[i][j] = s[j] - '0';
    }
  }
  dist[0][0][0] = 1; //false
  dist[0][0][1] = 1; //true
  q.push(make_tuple(0, 0, false));
  while(!q.empty())
  {
    tuple<int, int, bool> curr = q.front();
    q.pop();
    if(!get<2>(curr)){ //false dist
      for(auto i : dy){
        if(checkRange(get<0>(curr) + i, get<1>(curr), n, m)){
          //벽이 있다면
          if(map[get<0>(curr) + i][get<1>(curr)] == 1 && dist[get<0>(curr) + i][get<1>(curr)][1] == -1){
            dist[get<0>(curr) + i][get<1>(curr)][1] = dist[get<0>(curr)][get<1>(curr)][0] + 1;
            q.push(make_tuple(get<0>(curr) + i, get<1>(curr), true));
          }
          //벽이 없다면
          else if(map[get<0>(curr) + i][get<1>(curr)] == 0 && dist[get<0>(curr) + i][get<1>(curr)][0] == -1){
            dist[get<0>(curr) + i][get<1>(curr)][0] = dist[get<0>(curr)][get<1>(curr)][0] + 1;
            q.push(make_tuple(get<0>(curr) + i, get<1>(curr), false));
          }
        }
      }
      for(auto i : dx){
        if(checkRange(get<0>(curr), get<1>(curr) + i, n, m)){
          //벽이 있다면
          if(map[get<0>(curr)][get<1>(curr)+i] == 1 && dist[get<0>(curr)][get<1>(curr)+i][1] == -1){
            dist[get<0>(curr)][get<1>(curr)+i][1] = dist[get<0>(curr)][get<1>(curr)][0] + 1;
            q.push(make_tuple(get<0>(curr), get<1>(curr)+i, true));
          }
          //벽이 없다면
          else if(map[get<0>(curr)][get<1>(curr)+i] == 0 && dist[get<0>(curr)][get<1>(curr)+i][0] == -1){
            dist[get<0>(curr)][get<1>(curr)+i][0] = dist[get<0>(curr)][get<1>(curr)][0] + 1;
            q.push(make_tuple(get<0>(curr), get<1>(curr)+i, false));
          }
        }
      }
    }
    else
    { //true dist
      for(auto i : dy){
        if(checkRange(get<0>(curr) + i, get<1>(curr), n, m)){
          //벽이 없다면
          if(map[get<0>(curr) + i][get<1>(curr)] == 0 && dist[get<0>(curr) + i][get<1>(curr)][1] == -1){
            dist[get<0>(curr) + i][get<1>(curr)][1] = dist[get<0>(curr)][get<1>(curr)][1] + 1;
            q.push(make_tuple(get<0>(curr) + i, get<1>(curr), true));
          }
        }
      }
      for(auto i: dx){
        if(checkRange(get<0>(curr), get<1>(curr)+i, n, m)){
          //벽이 없다면
          if(map[get<0>(curr)][get<1>(curr)+i] == 0 && dist[get<0>(curr)][get<1>(curr)+i][1] == -1){
            dist[get<0>(curr)][get<1>(curr)+i][1] = dist[get<0>(curr)][get<1>(curr)][1] + 1;
            q.push(make_tuple(get<0>(curr), get<1>(curr)+i, true));
          }
        }
      }
    }
   
  }
  if(dist[n-1][m-1][0] == -1 && dist[n-1][m-1][1] == -1){
    cout << -1;
  }
  else if(dist[n-1][m-1][0] == -1){
    cout << dist[n-1][m-1][1];
  }
  else if(dist[n-1][m-1][1] == -1){
    cout << dist[n-1][m-1][0];
  }
  else{
    cout << min(dist[n-1][m-1][0], dist[n-1][m-1][1]); //마지막에는 짧은게 이김
  }
  
  return 0;
}
bool checkRange(int y, int x, int n, int m){
  if(y < 0 || y >= n || x < 0 || x >= m) return false;
  return true;
}

배운 점

bfs응용법을 또 배웠다.