[c++] 백준 #2206 벽 부수고 이동하기

1년 만의 백준 문제 풀기. 시작은 하게 골드4 정도의 만만한 BFS 문제로 골랐다.

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

일반적인 2차원 BFS 방식으로 다시 차근차근 구현하는데 한 시간 정도 걸렸고, 질문 검색에서 제안하는 디렉션을 읽고.. 최종 답 맞추기까지 1시간 45분 정도 걸렸다.

모든 벽을 다 한 번씩 부수면서 N*M번 BFS를 돌리면 계속 반복 계산하는 경우들 때문에 O(N^4)로 시간초과가 난다는 사실을 깨닫고

많은 질문 검색의 해답이 제안하듯, 벽을 부수는 케이스와 부수지 않는 케이스를 구별하여 3차원 DP행렬을 만들어버리는 식으로 풀었다. 

 

처음에는 한 번이라도 부순 경로와 한 번이라도 부수지 않은 경로를 구별하는 것이 조금 모호한 건 아닌가 생각을 했는데

코드로 짜보고 나니 별 게 없었다.

 

큐에 아이템을 넣으면서

1) 벽이 나왔을 때,

- 현재 큐에서 꺼낸 상태가 벽을 한 번도 안 부순 상태면 벽 부순 상태의 값을 큐에 넣어줌

- 이미 부쉈다면 그 상태는 거기서 끝.

 

2) 벽이 안 나왔으면 현재 상태가 벽이 부숴지든 안 부숴지든 그냥 진행하면 됨.

 

** 중간에 메모리 에러가 한 번 발생했는데, 방문한(곧 방문하기 위해 queue에 넣은 지점마저도) 지점을 미리 표시하지 않고 queue에서 꺼낼 때만 표시를 해서 한번 틀렸다. + 맨 처음 queue에 들어가는 아이템도 꺼내면서 표시해주는 것 잊지 말기!

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, ii, int> iiii;

#define MAX 1001

int my_map[MAX][MAX];
int cost[2][MAX][MAX];

int N, M;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};


void BFS(int x, int y, int passed_blocks){
  queue<iiii> q;
  q.push(make_tuple(0, make_pair(x, y), passed_blocks));

  while(!q.empty()){
    iiii front = q.front();
    q.pop();
    int broken = get<0>(front);
    int cx = get<1>(front).first;
    int cy = get<1>(front).second;
    int ct = get<2>(front);
    cost[broken][cx][cy] = min(cost[broken][cx][cy], ct);

    for(int i=0; i<4;i++){
        if (cx+dx[i] >= N or cx+dx[i] < 0)
          continue;
        if (cy+dy[i] >= M or cy+dy[i] < 0)
          continue;

        if (my_map[cx+dx[i]][cy+dy[i]] == 1){
          if (broken == 0)
            q.push(make_tuple(1, make_pair(cx+dx[i], cy+dy[i]), ct+1)); // break this time
          else
            continue;
        } 
        else {
          if (cost[broken][cx+dx[i]][cy+dy[i]] > (ct+1)){
            q.push(make_tuple(broken, make_pair(cx+dx[i], cy+dy[i]), ct+1));
            cost[broken][cx+dx[i]][cy+dy[i]] = ct + 1; // visited
          }
        }
    }
    
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // input parsing
  cin >> N >> M;
  for(int i=0; i<N;i++){
    string temp;
    cin >> temp;

    for(int j=0; j<M; j++){
      my_map[i][j] = temp[j] - '0';
    }
  }

  for (int a=0; a<2; a++){
    for (int i=0; i<N; i++){
      for (int j=0; j<M; j++){
        cost[a][i][j] = INF;
      }
    }
  }

  int ans = INF;
  // Do BFS
  BFS(0, 0, 1);
  ans = min(cost[1][N-1][M-1], cost[0][N-1][M-1]);
  if (ans == INF)
    ans = -1;
  cout << ans << '\n';

  return 0;
}