[BOJ/Gold 4] 백준 19952 인성 문제 있어??(C++)

문제 링크

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

19952번: 인성 문제 있어??

 

 

문제

인성이는 인싸가 되기 위해서 인싸트 특별과정에 참가했다. 훈련 첫날 인성이는 험난한 미로에서 목적지에 도달해야 하는 훈련을 받고 있다. 제한 시간 안에 미로를 통과하지 못하면 명기 교관 님에게 욕을 듣기에 인성이는 최선을 다해 미로를 통과하려고 한다.

미로는 가로 길이 W, 세로 길이 H의 격자 형태를 가지며, 인성이는 한 번에 격자 상의 상, 하, 좌, 우로 한칸 씩 움직일 수 있다.  매 이동이 완료될 시에 인성이의 남은 힘은 1씩 감소하고, 남은 힘이 0이하인 경우에는 더 이상 움직이지 못하게 된다.

미로의 각 격자에는 장애물이 있는데, 각각의 장애물은 높이 정보를 가지고 있다. 장애물이 없는 위치는 전부 높이가 0 이다. 인성이가 이동할 때, 현재 위치보다 이동할 위치의 높이가 더 낮으면 아무런 제약을 갖지 않고 이동할 수 있다. 더 높은 곳으로 이동할 때는 점프를 할 수 있는데, 점프해야 하는 높이는 (이동할 곳의 높이 - 현재 위치한 곳의 높이) 이다. 이때 남아있는 힘이 점프해야 하는 높이보다 크거나 같으면 이동할 수 있고, 그렇지 않으면 이동하지 못한다.

인성이는 신체적 한계를 극복하고 무사히 목적지에 도달해서 명기 교관님의 욕설을 듣지 않을 수 있을까?

입력

첫째 줄에 테스트 케이스 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫째 줄에 미로의 세로길이 H, 가로길이 W, 장애물의 개수 O, 초기 힘 F, 출발지의 좌표 정보 Xs(행), Ys(열)목적지의 좌표정보 Xe(행), Ye(열) 가 주어진다.

둘째 줄부터 O개의 줄에 장애물의 좌표 정보 X(행), Y(열) 와 높이 정보 L이 주어진다. 모든 장애물은 서로 다른 위치에 존재한다.

출력

T개의 줄에 인성이가 목적지에 도착할 수 있을 때 "잘했어!!", 목적지에 도착할 수 없을 때 "인성 문제있어??" 를 출력한다.

제한

• 1 ≤ T ≤ 10
• 2 ≤ H, W ≤ 100
• 0 ≤ O ≤ H x W
• 0 ≤ F ≤ 10,000, F 는 정수이다.
• 1 ≤ L ≤ 50, L은 정수이다.
• 1 ≤ X, Xs, Xe ≤ H
• 1 ≤ Y, Ys, Ye ≤ W
• 시작 위치와 목적지에는 장애물이 존재하지 않는다.

예제 입력 1

1
3 3 7 5 1 1 3 3
1 2 4
1 3 8
2 1 1
2 2 2
2 3 4
3 1 8
3 2 4

예제 출력 1

잘했어!!

예제 입력 2

1
3 5 3 6 1 1 3 5
1 2 8
2 1 8
3 1 4

예제 출력 2

인성 문제있어??

알고리즘 분류

• 그래프 탐색

풀이

장애물이 있는 O개의 좌표에 장애물의 높이를 기록한다.

그리고 BFS를 수행하는데, 현재 높이보다 다음 칸의 높이가 더 낮거나 같다면 그냥 힘을 1 감소시킨 채로 이동한다.

현재 높이보다 다음 칸의 높이가 더 높다면 높이의 차와 현재 힘을 비교하여, 현재 힘이 더 많거나 같다면 힘을 1 감소시킨 채로 이동하고, 현재 힘이 더 낮다면 이동하지 않는다.

다음 칸으로 이동했는데 힘이 0이 되었을 때, 목적지에 도착하지 못 했다면 다음 칸으로 이동할 수 없다.

힘이 0 미만으로 내려가기 전에 목적지에 도착했다면 잘했어!!를, 그렇지 않다면 인성 문제있어??를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int T, H, W, O, F, YS, XS, YE, XE;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            Visited[i][j] = false;
            MAP[i][j] = 0;
        }
    }
}

bool BFS() {
    queue<pair<pair<int, int>, int> > Q;
    Visited[YS][XS] = true;
    Q.push(make_pair(make_pair(YS, XS), F));

    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowF = Q.front().second;
        int NowH = MAP[NowY][NowX];
        Q.pop();

        if ((NowY == YE) && (NowX == XE)) {
            return true;
        }

        if (NowF == 0) {
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 1) && (NextY <= H) && (NextX >= 1) && (NextX <= W)) {
                if (NowH >= MAP[NextY][NextX]) {
                    if (!Visited[NextY][NextX]) {
                        Visited[NextY][NextX] = true;
                        Q.push(make_pair(make_pair(NextY, NextX), NowF - 1));
                    }
                }
                else {
                    int SubH = MAP[NextY][NextX] - NowH;
                    if (NowF >= SubH) {
                        if (!Visited[NextY][NextX]) {
                            Visited[NextY][NextX] = true;
                            Q.push(make_pair(make_pair(NextY, NextX), NowF - 1));
                        }
                    }
                }
            }
        }
    };

    return false;
}

void find_Answer() {
    bool Flag = BFS();
    if (Flag) {
        cout << "잘했어!!\n";
    }
    else {
        cout << "인성 문제있어??\n";
    }
}

void input() {
    cin >> T;
    while (T--) {
        init();
        cin >> H >> W >> O >> F >> YS >> XS >> YE >> XE;
        for (int i = 0; i < O; i++) {
            int A, B, C;
            cin >> A >> B >> C;
            MAP[A][B] = C;
        }
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}