#2206 벽 부수고 이동하기 (C++)

링크 : www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

고려해야할 조건은 다음과 같다.

(1) 이동하려는 다음 칸이 벽 && 아직 벽을 부순적이 없슴

     -> 벽을 부쉈다고 표시해주고 큐에 넣어서 다음 단계 진행

(2) 이동하려는 다음 칸이 벽 && 벽을 부순적이 있슴

     -> 진행 불가능. 큐에 넣지 않고 진행 -> 즉, 별도의 if문을 통해 작업이 진행되지 않는다.

(3) 이동하려는 다음 칸이 통로 && 아직 벽을 부순적이 없슴

     -> 벽을 부수지 않고 해당 정점을 방문한 적이 있는지 확인해주고, 아니라면 큐에 넣어서 다음 단계 진행 

(4) 이동하려는 다음 칸이 통로 && 벽을 부순적이 있슴

    -> 벽을 부수고 해당 정점을 방문한 적이 있는지 확인해주고, 아니라면 큐에 넣어서 다음 단계 진행 

 

조건이 4개나 되니까 복잡해 보이지만, 막상 코드를 짜면 조건은 단 2개로 귀결된다. 

3번과 4번의 경우 하나의 조건으로도 판결이 가능하기 때문이다.

 

처음에 문제를 풀고 통과율을 100%까지 찍는가 싶었으나, 번번히 실패를 겪었다. 

아래는 실패했던 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n = 0, m = 0, ny = 0, nx = 0;
int arr[1002][1002], my[4] = {1,0,-1,0}, mx[4] = {0,1,0,-1};
bool ch[1002][1002][2]; // 벽을 뚫고 방문한 경험과, 벽을 뚫지않고 방문한 경험을 나눔

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char c;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> c;
            arr[i][j] = c - 48;
        }
    }
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(1,1),make_pair(0,1))); //현재 위치 한 쌍 + 벽을 부순 횟수 + 누적 이동 횟수
    ch[1][1][0] = true;
    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int wall = q.front().second.first;
        int cnt = q.front().second.second;
        q.pop();

        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny==n&&nx==m){
                cout << cnt+1 << "\n";
                exit(0);
            }
            else if(ny>0&&ny<=n&&nx>0&&nx<=m){
                if(arr[ny][nx]==1 && wall==0){ // 다음 경로가 벽이지만 아직 한 번도 벽을 안뚫었다
                    ch[ny][nx][wall+1] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(wall+1,cnt+1)));
                }
                else if(arr[ny][nx]==0&&!ch[ny][nx][wall]){ //다음 경로가 통로고 해당 위치를 방문한 적이 없다
                    ch[ny][nx][wall] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(wall,cnt+1)));
                }
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

이 문제는 왜 틀렸을까? 이유는 다음의 테스트 케이스는 통과하지 못하기 때문이다.

1 1
0

정답은 1로 나와야하지만, 오류 코드에서는 위의 테스트 케이스의 결과가 -1로 출력되었다. 

 

시작부문 설정이 잘못되었음을 깨닫고 다시 수정을 진행했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n = 0, m = 0, ny = 0, nx = 0;
int arr[1002][1002], my[4] = {1,0,-1,0}, mx[4] = {0,1,0,-1};
bool ch[1002][1002][2]; // 벽을 뚫고 방문한 경험과, 벽을 뚫지않고 방문한 경험을 나눔

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char c;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> c;
            arr[i][j] = c - 48;
        }
    }
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(1,1),make_pair(0,1))); //현재 위치 한 쌍 + 벽을 부순 횟수 + 누적 이동 횟수
    ch[1][1][0] = true;
    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int wall = q.front().second.first;
        int cnt = q.front().second.second;
        q.pop();

        if(y==n&&x==m){
            cout << cnt << "\n";
            exit(0);
        }

        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];

            if(ny>0&&ny<=n&&nx>0&&nx<=m){
                if(arr[ny][nx]==1 && wall==0){ // 다음 경로가 벽이지만 아직 한 번도 벽을 안뚫었다
                    ch[ny][nx][wall+1] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(wall+1,cnt+1)));
                }
                else if(arr[ny][nx]==0&&!ch[ny][nx][wall]){ //다음 경로가 통로고 해당 위치를 방문한 적이 없다
                    ch[ny][nx][wall] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(wall,cnt+1)));
                }
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

역대급 메모리 차지율을 본 것 같은 느낌이다.