BOJ 9205 맥주 마시며 걸어가기

Hoyoung Jung·2020년 11월 17일

BOJ 9205 는 길찾기 문제이다.
정해진 기간마다 맥주를 마시면서 걷다 맥주가 부족해지기 전에 가게에 들려 맥주를 리필하고, 목적지를 찾아갈 수 있는지 여부를 출력해주면 된다.

풀이

맥주가 떨어지기 전에 갈 수 있는 최대거리는 1000미터이므로 BFS를 이용해서 1000미터 이내의 슈퍼를 방문하고 목적지까지 갈 수 있는지 여부를 확인하는 방법을 풀었다.

using namespace std;

bool canWalk(pair<int,int> &a, pair<int,int> &b) {
    return abs(a.first - b.first) + abs(a.second - b.second) <= 1000;
}

void bfs(vector<pair<int,int>> &a) {
    vector<bool> visited(a.size());
    queue <int> q;
    q.push(0);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        visited[curr] = true;
        for (int i = 1; i < a.size(); i++) {
            if (!visited[i] && canWalk(a[curr], a[i])) {
                if (i == a.size() - 1) {
                    cout << "happy\n";
                    return;
                }
                q.push(i);
            }
        }
    }
    cout << "sad\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        vector<pair<int, int>> a(n + 2);

        for (int i = 0; i < n + 2; i++) {
            cin >> a[i].first >> a[i].second;       
        }

        bfs(a);        
    };
    
    return 0;
}