[백준 9205] - 맥주 마시면서 걸어가기(C++)

📕문제

---

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

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

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

📕입력

---

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

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

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

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

📕출력

---

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

💻문제 해석

---

입력 테스트 케이스에 대한 고정관념을 버려야 한다.

나도 이러한 고정관념 덕분에 고생을 꽤나 했다. 처음에는 이 문제가 왜 BFS,DFS를 사용하는 문제지?라는 생각을 했다.

초기 나는 입력 테스트 케이스처럼 각 좌표가 거리가 먼순으로 차례대로 주어질줄 알았는데, 그것이 아니었다.

그리고 모든 편의점을 거칠 필요가 없다.

이러한 고정관념을 벗어나니 이 문제는 bfs로 푸는 것이 가장 효율적인 방법이라는 것을 알았다.

 

💡초기 풀이방식 

---

각 지점에서 다음 편의점까지 갈 수있는지에 대한 여부를 검사하고, 마지막 편의점까지 성공적으로 도착했다면, 도착 지점까지 갈 수 있는지에 대한 여부를 검사해서 sad와 happy를 출력했다.

-> 잘못된 풀이 방식.

이유 :

1) 입력받은 편의점 좌표들이 오름차순으로 정렬된 좌표가 아니다. [순서대로 탐색한다면 틀린 결과가 나옴]

2) 편의점들의 좌표보다 도착점의 좌표가 가까운 경우의 수가 있다. [모든 편의점을 방문할 이유가 없음

💡수정한 풀이 방식

---

1. 편의점과 도착점의 좌표를 모두 vector에 넣음.
2. queue에 초기 좌표를 넣고, 갈 수 있는 모든 지점에 좌표를 queue에 넣음.
   • 이 때 갈수있다는 기준은 초기좌표와 이동하려고 하는 좌표의 거리차가 1000이하면 이동가능
   • 만약 이동할 수 있다고 판단되면 queue에 넣고, vector에 해당 좌표를 지워줌.[방문을 했으니까!]
3. 초기 좌표를 queue에 front로 갱신해줌.
   • 1,2번 반복
4. queue를 계속 탐색하는데 만약 queue에 좌표가 도착지점과 일치하다면 happy를 출력
5. queue를 끝까지 탐색해도 도착지점까지 가지 못한다면 sad를 출력

💻코드

---

/*
9205 실버1 맥주 마시면서 걸어가기
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
int t, n,festivalX,festivalY;
vector<pair<int, int>> market;
queue<pair<int, int>> q;
void bfs(int x, int y);
int main()
{
    cin >> t;
    int homeX, homeY,step; //상근이 집
    for (int i = 0; i < t; i++)
    {
        market.resize(0); // vector초기화
        cin >> n;
        cin >> homeX >> homeY; //상근이 집
        for (int j = 0; j < n; j++)
        {
            int a, b;
            cin >> a >> b;
            market.push_back(make_pair(a, b));
        }
        cin >> festivalX >> festivalY;
        market.push_back(make_pair(festivalX,festivalY));
        bfs(homeX,homeY);
        //q초기화? 해줘야하나?
        while(!q.empty())
        {
            q.pop();
        }
    }
}
void bfs(int x, int y)
{
    q.push(make_pair(x, y)); // 기존 좌표 넣음/

    while (!q.empty())
    {
        auto fX = q.front().first;
        auto fY = q.front().second;
        q.pop();
        if(fX==festivalX && fY==festivalY)
        {
            cout<<"happy"<<endl;
            return;
        }
        for(int j=0; j<market.size();j++){
            int tempx,tempy;
            tempx=abs(fX-market[j].first);
            tempy=abs(fY-market[j].second);
            if(tempx+tempy<=1000)//거리가 1000이하면 갈 수 있는 모든 좌표를 입력함.
            {
                q.push(make_pair(market[j].first,market[j].second));
                market.erase(market.begin()+j); //j 지움.
                j--;
            }
            else{ //1000이상이면? 가지 못해요

            }
        }
    }
    //q가 완전히 빌 때 까지 도달하지 못하면 sad를 출력함.
    cout<<"sad"<<endl;
    return;
}

✔느낀점

• 문제를 정확하게 읽고 테스트 케이스를 생각해야 한다.
• 이상한 데서 핀트가 꽂혀서 문제를 지맘대로 해석하지 않기..
• 그라가스.