백준 9205 / 맥주 마시면서 걸어가기

굉장히 쉬운 문제인데 어렵게 해석해서 고생했던 문제다.

집 좌표와 편의점 좌표, 펜타포트 좌표를 받고.

BFS를 활용하여 펜타포트에 도착할수 있는지, 아니면 각 편의점에 도착할 수 있는지 판단하여

현재 지점에서 갈 수 있는 편의점의 위치를 큐에 넣어주면 된다.

편의점을 방문했는지 확인하는 bool 배열이 필요하다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<memory.h>
 
using namespace std;
 
bool check[103];
 
 
bool mat(int x, int y, int gx, int gy) {
 
    int dist = abs(gy - y) + abs(gx - x);
 
    if (dist <= 1000) {
        return true;
    }
 
    return false;
}
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    cin >> testcase;
 
    while (testcase--) {
 
        memset(check, false, sizeof(check));
 
        int shopnum;
        cin >> shopnum;
        vector<pair<int, int>>arr;
 
        for (int i = 0; i < shopnum + 2; i++) {
 
            int x, y;
 
            cin >> x >> y;
            arr.push_back(make_pair(x, y));
 
        }
 
        queue<pair<int, int>>q;
 
        q.push(make_pair(arr[0].first, arr[0].second));
        check[0] = true;
 
        bool ending = false;
 
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            int gx = arr[shopnum + 1].first;
            int gy = arr[shopnum + 1].second;
 
            if (mat(x, y, gx, gy) == true) {
                ending = true;
            }
 
            for (int i = 1; i < shopnum + 1; i++) {
                int sx = arr[i].first;
                int sy = arr[i].second;
 
                if (mat(x, y, sx, sy) == true && check[i] == false) {
                    check[i] = true;
                    q.push(make_pair(sx, sy));
                }
 
            }
        }
 
        if (ending == true) {
            cout << "happy" << endl;
        }
        else
            cout << "sad" << endl;
    }
}