[BOJ] 백준 9205 맥주 마시면서 걸어가기 c++ (bfs)

문제 출처 : https://www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

---

풀이

맥주 한 박스(20개)를 들고 50m마다 맥주를 한병씩 마시는데, 편의점에 방문하면 맥주를 채울 수 있다. 집에서 페스티벌 좌표까지 이동할 수 있는지 묻는 문제이다.

 

직관적으로 풀면 해결되는 문제였다. 먼저 맥주 20개를 가지고 있으니 최대 1000m까지 이동할 수 있다.

bfs로 풀면 이제 고려해야 할 경우는 2가지이다.

1. 1000m 맨해튼 거리 내 편의점이 있으면 큐에 추가

2. 1000m 맨해튼 거리 내 페스티벌 좌표가 있으면 happy 출력

3. 큐가 empty 상태가 되면 sad 출력

이때 주의할 점은 방문한 편의점은 방문처리를 해주어야 한다는 점이다! (중복 방지)

---

맨해튼 거리 계산

문제 그대로 x 좌표 차이 + y 좌표 차이를 구하면 된다. 따라서 차이에 절대값을 씌워 더해주면 된다.

// 페스티벌 좌표와 현재 위치의 맨해튼 거리
abs(festival.first - x) + abs(festival.second - y)

---

코드

#include <bits/stdc++.h>

using namespace std;

struct moves{
    int x;
    int y;
};

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int T; cin >> T;
    while (T--){
        int n; 
        pair<int, int> home, festival;

        cin >> n;
        cin >> home.first >> home.second;

        vector<pair<int, int>> store(n);
        vector<bool> visitStore(n, false);
        for(int i = 0; i < n; i++){
            cin >> store[i].first >> store[i].second;
        }
        cin >> festival.first >> festival.second;

        queue<moves> q;
        q.push({home.first, home.second});
        bool isHappy = false;
        while(!q.empty()){
            int x = q.front().x;
            int y = q.front().y;
            q.pop();

            // 편의점 1000m내에 있는지
            for(int i = 0; i < store.size(); i++)
                if((abs(store[i].first - x) + abs(store[i].second - y)) <= 1000){
                    if(!visitStore[i]){
                        visitStore[i] = true;
                        q.push({store[i].first, store[i].second});
                    }
                }

            if((abs(festival.first - x) + abs(festival.second - y)) <= 1000){
                isHappy = true;
                break;
            }
        }
        isHappy? cout << "happy" << '\n' : cout << "sad" << '\n';
    }
}