문제

• 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
  -> 충격적인 조건...
• n*m 행렬에서 0은 이동, 1은 벽
• (0,0) -> (n,m)까지 이동하는데 걸리는 최단 경로 출력

풀이

아... 입력받을 때 띄어쓰기가 없는것을 못봐서 엄청 헤맸다 ㅠㅠ

풀이 1 - segmentation fault

board의 인덱스 하나하나에 접근해서 벽을 허물어서 각 케이스에 최단 경로가 얼마가 나오는지 구해서 minimum을 비교한다.

#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];

int N, M;

void bfs(){
    queue<pair<int, int>> Q;
    Q.push({0,0});
    dist[0][0]=1;
        
    while(!Q.empty()){
        auto cur = Q.front();
        Q.pop();
        
        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.first+dx[dir];
            int ny = cur.second+dy[dir];
            
            //범위 확인하기
            if(nx<0||ny<0||nx>=N||ny>=M) continue;
            //방문했거나 벽이면 pass
            if(dist[nx][ny]>0 || board[nx][ny]=='1') continue;
            
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny});
            
        }
        
    }
}

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];
    
    
    //벽 안허물고 bfs 돌리기
    bfs();
    int nonbreak=-1;
    if(dist[N-1][M-1]!=0) nonbreak = dist[N-1][M-1]-1;
    fill(dist[0], dist[0]+1000, 0);
    
    //벽 허물어서 bfs 돌리기
    vector<int> tmp;
    int flag=0;
    for(int i=0; i<N; i++){
	    for(int j=0; j<M; j++){
    	    if(board[i][j]=='1'){
        	    board[i][j] = '0';
        	    bfs();
        	    if(dist[N-1][M-1]==0) board[i][j] = '1';continue;
        	    tmp.push_back(dist[N-1][M-1]-1); flag=1;
        	    board[i][j] = '1';
        	    fill(dist[0], dist[0]+1000, 0);
    	    }
	    }
    }
    
    if(flag ==0 && nonbreak==-1) cout <<-1;
    else if(nonbreak!=-1){ //벽 뚫는거랑 비교
        cout << min(nonbreak, *min_element(tmp.begin(), tmp.end()));
    }
    else{ //벽 뚫는게 최단시간 (벽 안뚫으면 길이 없음)
        cout << *min_element(tmp.begin(), tmp.end());
    }

    
  return 0;
}

            

일단 이 풀이는 for문을 두번 돌려서 시간초과가 나온다.

풀이 2 - 1인 곳만 bfs 돌리기

입력받을 때 1인 곳만 따로 벡터에 담아서 bfs를 돌렸는데 이것도 시간초과가 나온다.. ㅎㅎ

풀이 3 - 정답코드 (dist를 두개 두기)

벽을 부수지 않고 이동하는데 걸리는 시간을 dist[][][0]에 넣고 벽을 하나 부수고 이동하는데 걸리는 시간을 dist[][][1]에 넣는다.
벽을 하나만 부수는 것을 어떻게???
-> 벽을 부수는 경우에는 큐에 {nx, ny, 1}이렇게 마지막 원소에 벽을 부쉈다는 것을 명시해서 저장한다. 이후 위에서 벽을 부수는 여부를 결정하기 전에 마지막 원소인 broken을 확인하여 1이면 벽을 이미 부순 경우이기 때문에 벽을 부수지 않고 bfs를 돌려주고, 0이면 벽을 부수지 않은 경우이기 때문에 벽을 한번 부수고 bfs를 돌려준다.

정리
1. 큐에서 뽑아온 원소의 broken 상태를 확인한다.
2. broken이 1이면 이미 벽을 부순 상태 -> 그냥 bfs 돌려주기
3. broken이 0이면 벽을 부수지 않은 상태 -> 1을 만나면 벽을 부숴주고 해당 노드를 큐에 푸시해주기

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; //우선 방문하지 않았음을 명시하기 위해서 -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;
}

전체 코드

#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;
}