백준 17836 - 공주님을 구해라!(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

검을 얻었을 경우, 검을 얻지 못했을 경우로 나눠서 탐색을 진행해주는 것이 중요한 문제였습니다.

검을 얻었을 때는 벽을 제한없이 부실 수 있으며, 검을 얻지 못했을 경우는 정해진 길로밖에 가지 못합니다.

따라서 용사가 탐색을 하는 방법은

1. 검을 얻었을 경우

2. 검을 얻지 못했을 경우

이 2가지로 나눌 수 있습니다.

 

2가지 방법을 BFS에서 같이 돌려줘야 하는데, 경우가 다르니 방문여부도 다르게 저장해야 합니다.

저는 3차원 배열을 사용해서 (X,Y) 좌표에 도달할 경우를 2가지로 만들었습니다.(check[101][101][2]와 같습니다.)

 

먼저 (1,1)에서 용사가 출발하니 해당 지점에서 시작해줍니다.

이때는 검을 가지고 있지 않은 상태이니 0이라는 값을 가지고 시작해줍니다.(queue<PP> q를 보면 알 수 있습니다.)

 

BFS가 종료될 조건은 2가지입니다. 

1. T시간안에 공주를 찾았을 경우

2. T시간안에 못찾거나, queue가 모두 사라진 경우

1번 조건은 문제 조건과 같이 걸린 시간을 출력해주면 되고, 2번 경우는 -1를 return해, Fail을 출력하도록 했습니다.

 

4방향 탐색을 하는 중에서 검을 가진 여부에 따라서 다른 조건을 확인해야합니다.

검을 가지고 있는 경우는 어떤 벽이든 부술 수 있기에 해당 좌표에 벽이 있는지의 여부를 확인할 필요가 없습니다.

검을 가지고 있지 않는 경우에는 해당 좌표가 벽이 아닌지를 먼저 확인후 이동합니다. 이동한 좌표에 검이 있을 경우, 검을 주운 뒤, 검을 가졌다는 표시로 queue에 1의 값을 넣어줍니다.

 

해당 방법으로 탐색을 진행하면 답을 구할 수 있습니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#define P pair<int,int>
#define PP pair<P, P>
#define F first
#define S second
using namespace std;


int N, M, T;
int map[101][101];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int check[101][101][2];

int bfs(int X, int Y){
    queue<PP> q;
    q.push({{X,Y}, {0,0}}); // 현재 좌표, 걸린 시간, 검을 얻었는지 여부
    check[X][Y][0] = 1;
    while(!q.empty()){
        int x = q.front().F.F;
        int y = q.front().F.S;
        int t = q.front().S.F;
        int Sword = q.front().S.S;
        q.pop();
        if(t > T) break;
        if(x == N && y == M && t <= T) return t;
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(Sword == 1){
                    if(check[xx][yy][1] == 0){
                        check[xx][yy][1] = 1;
                        q.push({{xx,yy},{t+1, Sword}});
                    }
                }
                else{
                    if(map[xx][yy] != 1 && check[xx][yy][0] == 0){
                        if(map[xx][yy] == 2){
                            check[xx][yy][0] = 1;
                            q.push({{xx,yy},{t+1, Sword+1}});
                        }
                        else{
                            check[xx][yy][0] = 1;
                            q.push({{xx,yy},{t+1, Sword}});
                        }
                    }
                }
            }
        }
    }
    return -1;
}

void solve(){
    int ans = bfs(1,1);
    if(ans == -1) cout << "Fail";
    else cout << ans; 
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> T;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요