#17836번 공주님을 구해라! (C++)

문제 링크 : www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

문제 풀이는 다음과 같다.

(1) 벽을 부수고 방문하는 기록과 벽을 부수지 않고 방문하는 기록을 모두 저장할 수 있도록, 3차원 bool문을 만들어준다.

ex : bool ch[101][101][2] -> 여기서 맨 뒤의 2가 벽을 부쉈는지 아닌지를 결정한다.

(2) BFS를 진행한다. 이때 목표 지점인 (n,m)에 도달할 경우, 어차피 BFS는 가장 작은 값, 즉, 가장 빨리 목표에 도달하는 값이 출력되는 관계로 움직인 횟수를 출력하고 종료한다. 

(3) 다음 칸으로 이동해야 할 경우, 검이 있는 경우와 없는 경우를 나누어서 계산한다.

---

틀렸던 코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

int n=0,m=0,t=0, arr[101][101], ny=0, nx=0;
int my[4] = {1,0,-1,0}, mx[4] = {0,1,0,-1};
bool ch[101][101][2] = {false,};

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> t;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    queue<pair<pair<int,int>,pair<int,int>>> q; // 전자는 위치, 후자는 검을 갖고있는지와 지난 시간
    q.push(make_pair(make_pair(1,1),make_pair(0,0)));
    ch[1][1][0] = true;
    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int s = q.front().second.first; // 검의 여부
        int cnt = q.front().second.second; // 지난 시간
        q.pop();
        if(cnt>t) continue;
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny==n&&nx==m){
                if(cnt+1<=t){
                    cout << cnt + 1 << "\n";
                    exit(0);
                }
            }
            else if(ny>0&&ny<=n&&nx>0&&nx<=m){
                if(arr[ny][nx]==1&&s==1){ // 다음이 벽이고 검이 있는 경우
                    ch[ny][nx][s] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(1,cnt+1)));
                }
                else if(arr[ny][nx]==2&&!ch[ny][nx][s]){ // 다음이 검일경우
                    ch[ny][nx][s] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(1,cnt+1)));
                }
                else if(arr[ny][nx]==0&&!ch[ny][nx][s]){ // 다음이 통로인데 아직 방문경험이 없을 경우
                    ch[ny][nx][s] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(s,cnt+1)));
                }
            }
        }
    }
    cout << "Fail" << "\n";
   return 0;
}

이 코드는 계속해서 메모리 초과의 결과가 나왔다. 이유는 검이 있는 경우와 없는 경우를 잘 나누지 않은 상태로, 무작정 if - else if를 남발해서 그렇다.

 

---

정답 코드 

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

int n=0,m=0,t=0, arr[101][101], ny=0, nx=0;
int my[4] = {1,0,-1,0}, mx[4] = {0,1,0,-1};
bool ch[101][101][2] = {false,};

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> t;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    queue<pair<pair<int,int>,pair<int,int>>> q; // 전자는 위치, 후자는 검의 여부와 경과 시간
    q.push(make_pair(make_pair(1,1),make_pair(0,0)));
    ch[1][1][0] = true, ch[1][1][1] = true;
    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int s = q.front().second.first; // 검의 여부
        int cnt = q.front().second.second; // 지난 시간
        q.pop();
        if(cnt>t) continue;
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny==n&&nx==m){
                if(cnt+1<=t){
                    cout << cnt + 1 << "\n";
                    exit(0);
                }
            }
            else if(ny>0&&ny<=n&&nx>0&&nx<=m){
                if(s==1){ // 검이 있음
                    if(arr[ny][nx]==1&&!ch[ny][nx][s]){
                        ch[ny][nx][s] = true;
                        q.push(make_pair(make_pair(ny,nx),make_pair(s,cnt+1)));
                    }
                    else if(arr[ny][nx]==0&&!ch[ny][nx][s]){
                        ch[ny][nx][s] = true;
                        q.push(make_pair(make_pair(ny,nx),make_pair(s,cnt+1)));
                    } else continue;
                }
                else{ // 검이 없음
                    if(arr[ny][nx]==1) continue;
                    else if(arr[ny][nx]==0&&!ch[ny][nx][s]){
                        ch[ny][nx][s] = true;
                        q.push(make_pair(make_pair(ny,nx),make_pair(s,cnt+1)));
                    }
                    else if(arr[ny][nx]==2&&!ch[ny][nx][s]){
                        ch[ny][nx][s] = true, ch[ny][nx][1] = true;
                        q.push(make_pair(make_pair(ny,nx),make_pair(1,cnt+1)));
                    } else continue;
                }
            }
        }
    }
    cout << "Fail" << "\n";
   return 0;
}

 

추가로 이 문제는 백준 2206번 벽 부수고 이동하기와 비슷하니, 함께 풀어보는 것을 권장한다.