백준 2206 벽부수고 이동하기 - 이제는 3차원 visited 배열이 필요하다. c++

문제링크

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

2206번: 벽 부수고 이동하기

해결 과정

컨셉이 비슷한 문제로 다음과 같은 문제가 있다.

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

1261번: 알고스팟

위 알고스팟문제와 벽부수고 이동하기의 문제의 공통점은 벽을 부수고 이동하겠다는 컨셉이 똑같다는 것이다.

하지만 큰 차이는 알고스팟 문제는, 벽을 무한번 부술수 있고 그 부순 횟수를 구하는 것이라면, 

벽부수고 이동하기 문제는 벽을 한번밖에 못부순다는 점이다.

 

처음에는 단순하게, 전형적인 bfs문제 푸는 방식을 이용해서 풀겠다는 아이디어를 가졌다.

당연하게도 최단경로 문제였기 때문이다.

하지만 코드를 제출했을때 결과를 보니 틀렸다고 나왔다.

테스트 케이스는 전부 통과한 상태에서 제출했는데도 틀렸다고 나와서 좀 당황했었다.

 

틀린 이유를 후에 분석해보니, 단순히 bfs를 이용해서 풀게 되면 

이미 벽을 부수고 이동한 상태에서 visited는 true가 되기 때문에, 벽을 안부수고 이동할 수 있는 문제를 풀 수 있는 경우가 존재하는데도 이를 인지하지 못하고 -1을 반환하는 문제가 생기기 때문에 이를 전부 고려해서 문제를 풀었어야 했다.

 

다음은 내가 처음 낸 틀린 코드와 반례이다.

#include <iostream>
#include <queue>
using namespace std;
int n,m;
int map[1001][1001];
int visited[1001][1001];
 
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
int bfs(int y, int x, int life){
 
    int answer=1;
    queue<pair<pair<int,int>,int>> q;
    q.push(make_pair(make_pair(y,x),life));
    visited[y][x]=1;
    while(!q.empty()){
        int size = q.size();
//        cout<<size<<"\n";
        answer++;
        for(int it=0; it<size; it++) {
            int yy = q.front().first.first;
            int xx = q.front().first.second;
//            cout<<xx<<" "<<yy<<"\n";
            int lif = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int ny = yy + dy[i];
                int nx = xx + dx[i];
                if(ny>=0 && ny<n && nx>=0 && nx<m && !visited[ny][nx]){
                    if(map[ny][nx]==1 && lif==1){
                        visited[ny][nx]=1;
                        q.push(make_pair(make_pair(ny,nx),lif-1));
//                        visited[ny][nx]=0;
                    }
                    if(map[ny][nx]==0){
                        visited[ny][nx]=1;
                        q.push(make_pair(make_pair(ny,nx),lif));
//                        visited[ny][nx]=0;
                    }
                    if(ny==n-1 && nx==m-1) return answer;
                }
            }
        }
    }
    return -1;
 
}
 
 
int main(void){
    cin>>n>>m;
    string s;
    for(int i=0; i<n;i++) {
        cin >> s;
        for(int j=0; j<m;j++){
            map[i][j] = s[j]-'0';
        }
    }
    cout<<bfs(0,0,1);
}

반례 :

6 3
000
110
000
011
111
000

(벽을 한번만 부수고 갈 수 있는 경로가 존재하지만 -1이 반환된다. 정답은 12.)

 

이를 해결하기 위해 33,38번째 line에서 visited 값을 다시 0으로 바꿔줌으로써 가능한 모든 경로를 탐색할 수 있는 방식을 이용하려고 했다. 

주석을 풀고 코드를 돌려보면 반례의 경우 12가 잘 나온다.

 

하지만 저 주석을 풀고 코드를 제출하게 될 경우 메모리 초과가 떠서 문제를 풀 수 없다.

 

어떻게 해결할 지 고민 하면서 코드를 찾아보던중, visited 배열을 3차원으로 두고 푸는 풀이를 발견했다.

메모리의 양을 2배만 증가 시키고(0,1 만 고려하면 되므로) 풀 수 있는 획기적인 방법이었다.

 

최단경로 문제의 경우 움직임에 제약이 있는 추가 조건이 있는 경우, 3차원 배열을 이용하는 방식을 고려해보자.

 

#include <iostream>
#include <queue>
using namespace std;
int n,m;
int map[1001][1001];
bool visited[1001][1001][2];
 
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
int bfs()
{
    queue<pair<pair<int, int>, pair<int,int>>> Q;
    Q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
    visited[0][0][0] = true;
 
    while (!Q.empty())
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int B = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        if (x == n - 1 && y == m - 1)
        {
            return Cnt;
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < m)
            {
                if (map[nx][ny] == 1 && B == 0)
                {
                    visited[nx][ny][B+1] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(B + 1, Cnt + 1)));
                }
                else if (map[nx][ny] == 0 && visited[nx][ny][B] == false)
                {
                    visited[nx][ny][B] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(B, Cnt + 1)));
                }
            }
        }
    }
    return -1;
}
 
 
 
 
int main(void){
    cin>>n>>m;
    string s;
    for(int i=0; i<n;i++) {
        cin >> s;
        for(int j=0; j<m;j++){
            map[i][j] = s[j]-'0';
        }
    }
    cout<<bfs();
}