[BAEKJOON] 19952. 인성 문제 있어??

Posted on October 01, 2020

문제 :

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

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

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

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

입력 :

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

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

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

출력 :

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

풀이 :

우선 문제 이름이 흥미로워서 풀어본게 큰 것 같다. 요즘 이근 대위가 핫한만큼… 문제도 핫할려나 싶었는데 문제내용은 생각외로 싱거웠던 것 같다. 문제는 전형적으로 bfs 방식을 사용해 미로찾기 풀이를 사용하면 쉽게 풀리는 문제 같았다.

우선 미로 출발 위치와 도착위치를 입력받고 장애물 위치를 입력받는데 장애물은 무조건 못지나가는 것이 아니고 현재 남아있는 힘 이하의 높이 장애물은 뛰어넘을 수 있게 코딩해야했다.

그래서 bfs방식을 사용하여 큐에 가능한 경로를 저장하면서 장애물을 만났을 때에는 현재 남은 힘과 비교하여 큐에 넣을지 말지 결정해주었다. 장애물의 경우 말고는 무난한 문제였던 것 같다.

코드 :

코드 보기/접기

#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#define pii pair<int, int>

using namespace std;
int map[101][101], h, w, f, startx, starty, finx, finy, di[4] = { 0, 1, 0, -1 }, dj[4] = { 1, 0, -1, 0 };

bool findPath() {
    queue<pii> q;
    int curx, cury, k, cmpx, cmpy, size;
    bool visit[101][101]{ false };
    q.push(pii(startx, starty));
    visit[startx][starty] = true;
    while (!q.empty()) {
        size = q.size();
        while (size--) {
            curx = q.front().first; cury = q.front().second;
            if (curx == finx && cury == finy)   return true;
            q.pop();
            for (k = 0; k < 4; k++) {
                cmpx = curx + di[k];  cmpy = cury + dj[k];
                if (0 < cmpx && cmpx <= h && 0 < cmpy && cmpy <= w && !visit[cmpx][cmpy] && map[cmpx][cmpy] - map[curx][cury] <= f) {
                    q.push(pii(cmpx, cmpy));
                    visit[cmpx][cmpy] = true;
                }
            }
        }
        f--;
    }
    return false;
}

void testCase() {
    int o, cmpx, cmpy, val;
    cin >> h >> w >> o >> f >> startx >> starty >> finx >> finy;
    memset(map, 0, sizeof(map));
    while (o--) {
        cin >> cmpx >> cmpy >> val;
        map[cmpx][cmpy] = val;
    }
    if (findPath()) cout << "잘했어!!" << '\n';
    else cout << "인성 문제있어??" << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);  cin.tie(NULL);  cout.tie(NULL);
    int tc;
    cin >> tc;
    while (tc--)
        testCase();
    return 0;
}

Algorithm

algorithm baekjoon C++