[2206👍] 벽 부수고 이동하기

내 코드

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int field[1001][1001];
int dist[1001][1001];
int xdir[4] = {1,0,-1,0};
int ydir[4] = {0,1,0,-1};
int m,n;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
        {
            string str; cin >> str;
            dist[i][j] = -1;
            field[i][j] = str[j-1] - '0';
        }
    }
    queue<pair<int,int>> q;
    q.push({1,1}); 
    dist[1][1] = 1;
    
    while(!q.empty())
    {
        pair<int,int> cur = q.front(); q.pop();
        int broke = 0;
        for(int i = 0;i<4;i++)
        {
            int curx = cur.first + xdir[i];
            int cury = cur.second + ydir[i];
            if(curx<1||curx>=n||cury<1||cury>=m) continue;
            if(field[curx][cury] == 1 && broke == 0)
            {
                broke++;
                field[curx][cury] = 0;
                dist[curx][cury] = dist[cur.first][cur.second] + 1;
                q.push({curx,cury});
                continue;
            }
            if(dist[curx][cury] >= 1 || field[curx][cury] == 1) continue;
            q.push({curx,cury});
            dist[curx][cury] = dist[cur.first][cur.second] + 1;
            if(curx == n && curx == m)
            {
                cout << dist[curx][cury];
                return 0;
            }
        }
    }
    cout << -1;
    
}

---

첫번째 시도에서 오답이 나오고, 두번째 시도에서는 시간초과가 나왔다. 결과적으로는 실패 ㅠ
첫번째 시도에서는 벽을 부쉈는지 안부쉈는지 체크하는 전역변수를 하나 만들어서 bfs의 if 문에서 field가 1 일때 전역변수를 +1 하여 구성하였으나, 실패했다.

두번째 시도에서는 field 에 1 의 위치를 deque 에 저장하고 deque 에서 뽑아 field 를 하나씩 0 으로 바꿔 bfs 를 돌리면서 최소값을 찾고자 하였으나 시간초과로 실패했다.

---

정답

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

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

char board[1000][1000];
int dist[1000][1000][2];
// dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용
// dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함
int n, m;

bool OOB(int x, int y){
  return x < 0 || x >= n || y < 0 || y >= m;
}

int bfs() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      dist[i][j][0] = dist[i][j][1] = -1;
  dist[0][0][0] = dist[0][0][1] = 1;
  queue<tuple<int, int, int>> q;
  q.push({0,0,0});
  while (!q.empty()) {
    int x, y, broken;
    tie(x, y, broken) = q.front();
    if(x == n-1 && y == m-1) return dist[x][y][broken];
    q.pop();
    int nextdist = dist[x][y][broken] + 1;
    for (int dir = 0; dir < 4; ++dir) {
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if(OOB(nx, ny)) continue;      
      if (board[nx][ny] == '0' && dist[nx][ny][broken] == -1) {
        dist[nx][ny][broken] = nextdist;
        q.push({nx, ny, broken});
      }      
      // (nx, ny)를 부수는 경우
      if (!broken && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
        dist[nx][ny][1] = nextdist;
        q.push({nx, ny, 1});
      }      
    }
  }
  return -1;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      cin >> board[i][j];
  cout << bfs();
  return 0;
}

처음에 보았을떄는 이해가 안되었으나, 하나씩 곱씹어보니 진짜 기발한 코드다.. ㅠㅠ (언제 이정도 실력이 될까)
배열을 1층이 아닌 2층으로 선언해 1층에는 벽을 통과하지 않읂 경우, 2층에는 통과한 경우이다. 즉, 1층에서 움직이다가 최초로 벽에 닿을시 에 2층으로 올라가는 것이다. 여러 차례 생각해봐도 진짜 깔끔하다....