벽 부수고 이동하기

코드

[ 시간초과 코드 ]

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std; 
char board[1001][1001];
int cost[1001][1001];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 , -1, 0};
int ans = 1e9;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    vector<pair<int,int>> v;
    vector<pair<int,int>> real;
    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == '1')
                v.push_back({i,j});
        }
    for(int i=0;i<v.size();i++)
    {
        auto cur = v[i];
        int cnt=0;
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
            if(board[ny][nx] != '1') cnt++;
        }
        if(cnt >= 2)
            real.push_back(v[i]);
    }
    for(int i=0;i<real.size();i++)
    {
        board[real[i].first][real[i].second] = '0';
        queue<pair<int,int>> q;
        q.push({0,0});
        cost[0][0] = 1;
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
                if(board[ny][nx] == '1') continue;
                if(cost[ny][nx] != 0 and (cost[ny][nx] < cost[cur.first][cur.second]+1)) continue;
                q.push({ny, nx});
                cost[ny][nx] = cost[cur.first][cur.second] + 1;
                if(ny == N-1 and nx == M-1) goto stop;
            }
        }
        stop:
        if(cost[N-1][M-1] != 0)
            ans = min(ans, cost[N-1][M-1]);
        board[real[i].first][real[i].second] = '1';
    }
    if(ans == 1e9) cout << -1;
    else cout << ans;
    return 0;
}

• 로직
  • '1'이 들어간 모든 좌표에 대해 하나씩 값을 바꿔보며 BFS를 수행해 최소값을 찾기
• 실패 이유
  : 시간초과

---

[ 정답 풀이 ]

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define INF 1e9
using namespace std;
char board[1001][1001];
int cost[2][1001][1001];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 , -1, 0};
queue<pair<pair<int,int>,int>> q;
int ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> board[i][j];

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

    q.push({{0,0},0});
    cost[0][0][0] = 1;
    cost[1][0][0] = 1;
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.first.first + dy[dir];
            int nx = cur.first.second + dx[dir];
            int status = cur.second;
            if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
            if(board[ny][nx] == '1'){
                if(status == 0) status=1;
                else continue;
            }
            if(cost[status][ny][nx] <= cost[cur.second][cur.first.first][cur.first.second]+1) continue;
            q.push({{ny, nx}, status});
            cost[status][ny][nx] = cost[cur.second][cur.first.first][cur.first.second] + 1;
            if(ny == N-1 and nx == M-1) goto stop;
        }
    }
    stop:
    ans = min(cost[0][N-1][M-1], cost[1][N-1][M-1]);
    if(ans == INF) cout << -1;
    else cout << ans;
    return 0;
}

• 핵심
  • board[N][M]의 입장에서 각 칸은 벽을 부수고 온 경우 / 벽을 부수지 않고 온 경우로 2가지가 존재
    --> cost[2][N][M] 으로 각 상태에 따른 최단 경로를 저장해야 함
  • queue에 status값도 함께 포함
    (queue<pair<pair<int,int>,int>> q)