# 9205. 맥주 마시면서 걸어가기

관련 알고리즘 : BFS

 

문제 링크 : https://www.acmicpc.net/problem/9205

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

---

문제 풀이

 

<문제 조건>

 

• 한 박스 : 맥주 20개 최대
• ( 맥주마시기 ) => 50미터 O
• 빈 병 버리고 새 맥주병( 맥주병 최대 20개 )
• 테스트 케이스 개수 t ( t <= 50 )
• 편의점 개수 n
• 두 좌표 사이의 거리 : ( x좌표의 차이 ) + ( y좌표의 차이 )

맥주병을 최대 20개가 있고, 한 병 마실 때마다 최대 50미터를 갈 수 있으므로,

편의점 없이 최대로 갈 수 있는 거리는 50x20 = 1000m 이다.

=> 두 좌표 사이의 거리가 1000m 이하면 이동 가능

 

1. 1000m 거리 내 편의점 있음 => queue에 추가
2. queue가 empty => sad 출력

---

C++ 코드

#include <iostream>
#include <queue>

using namespace std;

struct coo
{
    int x; int y;
};

coo store[100];   // 편의점 좌표(0 <= 편의점 개수 <= 100)
coo festival;     // 페스티벌 좌표
coo home;         // 집 좌표
bool visited[100];

// 절댓값 계산
int abs(int n) {
    if (n < 0) 
        return -n;
    return n;
}

bool bfs(int n) {
    queue<pair<int, int>> que;
    que.push({home.x, home.y}); 

    while (!que.empty()) {
        int x = que.front().first; 
        int y = que.front().second;
        que.pop();

        if (abs(festival.x - x) + abs(festival.y - y) <= 1000) 
            return true; // 거리 1000m 이하일 경우 이동 가능
        for (int i = 0; i < n; i++) {
            if (visited[i]) { // 방문했던 편의점일 시,
                continue;
            }
            if (abs(store[i].x - x) + abs(store[i].y - y) <= 1000) {        
                visited[i] = true;                                             
                que.push({store[i].x, store[i].y});                        
            }
        }
    }
    return false; // while 다 돌았는데도 도착 못했으면 false
}

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0); 
    cin.tie(0);

    int t;  // test 개수
    cin >> t;

    while(t--) {
        int n; 
        cin >> n;

        cin >> home.x >> home.y;                
        for (int i=0; i < n; i++) {
            cin >> store[i].x >> store[i].y;    
        }
        cin >> festival.x >> festival.y;        

        bool possible = bfs(n);
        if(possible) cout << "happy\n";
        else cout << "sad\n";

        fill(visited, visited+100, false); // visited bool check false로 초기화
    }

    return 0;
}