[백준] 27583번: Hunt the Wumpus - C++

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

 

영어 문제니 간단하게 요약해보면

 

1. $10 \times 10$ 크기의 그리드에 4개의 Wumpus 가 있다.
2. 정수 $s$를 규칙에 맞춰 업데이트하고, 아래 2자리를 각각 $x, y$좌표로 삼는다.
3. 주어진 입력의 좌표로 이동했을 때 wumpus가 있다면 wumpus를 잡았다고 출력한다.
4. 가장 가까이 있는 wumpus의 맨해튼 거리를 (있다면) 출력한다.

조심해 주어야 할 부분은 "The first four distinct numbers generated" 즉, $s$에서 wumpus의 위치를 만들 때 똑같은 위치가 나오면 안된다는 것이다.(당연한 건데 이걸 놓쳐서 정답률 100% 문제였는데 오답을 제출해 버렸다 ㅜㅜ).

 

wumpus 위치 구하기

$s$를 $s + \left\lfloor \frac{s}{13} \right\rfloor + 15$로 업데이트 하고 아래 2자리를 저장한다.

for (int i = 0; i < 4; i++) {
    do {
        s = s + s / 13 + 15;
        loc[i] = s % 100;
    } while (find(loc, loc + i, loc[i]) != loc + i);
}

최대 4개 밖에 없으니 완전탐색해 중복을 체크해주었다.

참고로 아래 두자리를 그대로 저장했으니 거리는 아래와 같이 구할 수 있다.

int dist(int a, int b) {
    return abs(a / 10 - b / 10) + abs(a % 10 - b % 10);
}

 

이동 처리

이제 이동이 발생할 때마다 현재 위치에 wumpus가 있는지 검사하고 가장 가까운 발견하지 못한 wumpus와의 거리를 출력하면 된다.

 

전체 코드

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

int dist(int a, int b) {
    return abs(a / 10 - b / 10) + abs(a % 10 - b % 10);
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    long long s;
    cin >> s;

    int loc[4], hitCnt = 0, m = 0;
    bool hit[4] = {};

    for (int i = 0; i < 4; i++) {
        do {
            s = s + s / 13 + 15;
            loc[i] = s % 100;
        } while (find(loc, loc + i, loc[i]) != loc + i);
    }

    while (hitCnt < 4) {
        int x;
        cin >> x;
        m++;

        for (int i = 0; i < 4; i++) {
            if (!hit[i] && loc[i] == x) {
                cout << "You hit a wumpus!\n";
                hit[i] = true;
                hitCnt++;
                break;
            }
        }

        int near = 100;
        for (int i = 0; i < 4; i++)
            if (!hit[i])
                near = min(near, dist(x, loc[i]));
        if (near == 100) break;
        cout << near << '\n';
    }

    cout << "Your score is " << m << " moves.\n";
}