맥주 마시면서 걸어가기 9205번 (BFS)

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

https://www.acmicpc.net/problem/9205

 

기본적인 BFS()문제인데 맨허튼 거리라서 좀 쉽게 풀린 거같다. 만약 유클리드 거리 방식으로 문제를 풀었다고 하면 식만 좀더 변형하면 될거같다.

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	2096	680	532	33.671%

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다.

예제 입력 1

 
xxxxxxxxxx
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

예제 출력 1

 
happy
sad

 

소스 코드

 
​x
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
​
int t;  // 테스트케이스 수
int n;  // 편의점 갯수
int me_y, me_x;     // 상근이네 집 좌표
vector<pair<int, int>> cu;  // 편이점 좌표
int lock_y, lock_x;     // 락 페스티벌 좌표
int res;
​
void BFS()
{
    queue<pair<int, int>> q;
    q.push({ me_y,me_x });
    int chk[100] = {0}; // 편의점 체크용
    res = 0;
    while (1)
    {
        if (q.empty() || res == 1) break;
        int here_y = q.front().first;
        int here_x = q.front().second;
        q.pop();
​
        for (int i = 0; i < cu.size(); i++)
        {
            if (abs(here_y - cu[i].first) + abs(here_x - cu[i].second) <= 1000 && chk[i] == 0)  // 편의점에 도달 할 수 있을 때
            {
                q.push({ cu[i].first , cu[i].second });
                chk[i] = 1;
            }
            else if (abs(here_y - lock_y) + abs(here_x - lock_x) <= 1000)   // 현재 위치에서 락 페스티벌 까지 도달 할 수 있을 경우
                res = 1;
        }
    }
}
​
void input()
{
    cin >> t;
    for (int k = 0; k < t; k++)
    {
        cu.clear();
        cin >> n;
        cin >> me_y >> me_x;
        for (int i = 0; i < n; i++)
        {
            int y, x;
            cin >> y >> x;
            cu.push_back({ y,x });
        }
        cin >> lock_y >> lock_x;
        BFS();
        if (res == 1) cout << "happy" << '\n';
        else cout << "sad" << '\n';
    }
}
​
int main()
{
    input();
​
    return 0;
}