백준 : 9205번 맥주 마시면서 걸어가기BFS c++

백준 링크

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	28075	11478	8381	39.700%

문제

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

happy
sad

BFS 코드 풀이

 이번 문제는 BFS 풀이로 풀이하는데 기본 경로 탐색이랑 다르게 한 칸씩 전진하면서 Dist를 찾는게 아닌 Store 좌표의 배열을 순회하면서 거리별 허용치를 기준으로 주어 탐색하는것이다.

문제에 보면 맥주 상자에 맥주가 최대 20개 들어있고 편의점에 가면서 50미터에 한 병씩 마신다고 하면 최대 1천 미터 이동이 가능한 것이다 그래서 [맨해튼 거리(가야 할 위치.x - 현재 위치.x)  + (가야할 위치.y - 현재 위치.x)]가 1천 이하이고 방문하지 않은 편의점이라면 큐에 값을 넣고 최종적으로 플래그를 설정해  happy, sad를 출력하는 bfs 코드를 구성하면 되는 것입니다.

이때 거리는 abs()를 이용해 절댓값으로 계산해야 한다. (편의점 위치가 오름차순으로 정렬되어 있다는 보장이 없음)

자세한 내용은 주석 참고해 주세요

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

// 계산된 두 좌표 사이의 맨해튼 거리를 반환하는 함수
int Dist(pair<int, int> a, pair<int, int> b) 
{
    return abs(b.first - a.first) + abs(b.second - a.second);
}

int main()
{
    // 테스트 케이스 개수
    int T;
    cin >> T;

    // 각 테스트 케이스마다 실행
    while (T--) 
    {
        int N;
        cin >> N;

        vector<pair<int, int>> Store;

        // 각 좌표를 방문했는지 저장하는 배열
        bool Visited[102] = {};

        for (int i = 0; i < N + 2; ++i)
        {
            pair<int, int> Pos;
            cin >> Pos.first >> Pos.second;
            Store.push_back(Pos);
        }

        queue<pair<int, int>> q;
        q.push(Store[0]);

        // 페스티벌에 도착할 수 있는지 나타내는 플래그
        bool canGo = false;
        while (!q.empty()) 
        {
            auto current = q.front();
            q.pop();

            // 현재 좌표가 페스티벌의 좌표라면 플래그를 설정하고 반복문을 종료
            if (current == Store[N + 1]) 
            {
                canGo = true;
                break;
            }

            for (int i = 1; i < N + 2; i++)
            {
                // 아직 방문하지 않았고, 현재 좌표로부터 거리가 1000 이하라면
                if (!Visited[i] && Dist(current, Store[i]) <= 1000)
                {
                    // 해당 좌표를 방문했다고 표시하고
                    Visited[i] = true;
                    q.push(Store[i]);
                }
            }
        }

        if (canGo) 
            cout << "happy\n";
        else 
            cout << "sad\n";
    }

    return 0;
}