맥주 마시면서 걸어가기 9205

문제

접근 방법

문제에서는 20병 50미터를 이야기하였지만 결국에는 1000미터 안에 있는 곳만 갈 수 있다는 뜻이다. (1000미터 안에 있는 편의점에 들어가면 리필이 되므로 기존의 병은 상관없다)
1000미터 안에 들어가는지 확인하며 BFS를 돌리면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    int t;
    cin >> t;
    bool isVisted[101];
    pair<int, int> store[101], start, dest;
    while (t--)
    {
        queue<pair<int, int>> bfs;
        int n;
        cin >> n;
        cin >> start.first >> start.second;
        for (int i = 0; i < n; ++i)
        {
            cin >> store[i].first >> store[i].second;
            isVisted[i] = false;
        }
        cin >> dest.first >> dest.second;

        bfs.push(start);
        while (!bfs.empty())
        {
            auto cur = bfs.front();
            if (abs(dest.first - cur.first) + abs(dest.second - cur.second) <= 1000)
            {
                break;
            }
            bfs.pop();
            for (int i = 0; i < n; ++i)
            {
                if (isVisted[i])
                    continue;
                auto next = store[i];
                if (abs(next.first - cur.first) + abs(next.second - cur.second) > 1000)
                    continue;
                bfs.push(next);
                isVisted[i] = true;
            }
        }
        if (bfs.empty())
            cout << "sad";
        else
            cout << "happy";
        cout << "\n";
    }
    return 0;
}

풀이

목적지에 도달할 수 있다면 pop하지 않고 반복문에서 나와 큐에 남겨두었다. 즉 큐에 있는 것이 다 사용되더라도 도달 못 한 경우에는 sad가 출력되고 큐에 하나라도 남는다면 happy가 출력된다.