[C++/백준/BFS] 9205번 맥주 마시면서 걸어가기

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

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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 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문제입니다. 이번에는 x,y 좌표 모두 관리해야하기 때문에 ST struct구조체를 선언해 x,y좌표를 편하게 관리해줍니다.

struct ST
{
    int x;
    int y;
};
ST store[100];
ST goal;
ST home;
bool visited[100];

방문 기록은 편의점을 방문하면 병을 다시 채우기 때문에 편의점을 들릴때마다 해당 편의점으로 돌아가지 않기 위해 방문 처리를 해줍니다. 넓이 우선 탐색(bfs)를 하면서 만약 큐에서 꺼낸 좌표와 goal 좌표의 차이가 1000보다 작거나 같다면 goal에 남은 맥주로 도달할 수 있다는 뜻이니 true를 return해줍니다. 하지만 모든 편의점을 방문할동안 해당 조건문에 걸리지 않는다면 결국 queue에 있는 값들이 다 소모되어 반복문이 끝나고 false를 return 합니다.

 

전체소스코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int t,n;

struct ST
{
    int x;
    int y;
};
ST store[100];
ST goal;
ST home;
bool visited[100];





bool bfs(int x,int y)
{
    queue<pair<int,int>>q;
    q.push(make_pair(x,y));
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        if(abs(x-goal.x)+abs(y-goal.y)<=1000)
            return true;
        for(int i=0;i<n;i++)
        {
            if(visited[i]==false)
            {
                if(abs(x-store[i].x)+abs(y-store[i].y)<=1000)
                {
                    int nx = store[i].x;
                    int ny = store[i].y;
                    q.push(make_pair(nx,ny));
                    visited[i] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
   cin>>t;
  
   
   while(t--)
   {
       cin>>n;
       memset(visited,false,sizeof(visited));
       cin>>home.x>>home.y;
       for(int i=0;i<n;i++)
       {
            cin>>store[i].x>>store[i].y;
       }
       cin>>goal.x>>goal.y;
       
       if(bfs(home.x,home.y))
            cout<<"happy"<<endl;
       else
            cout<<"sad"<<endl;
   }
    return 0;
}

이번 문제같은 경우는 하나의 테스트케이스가 아닌 여러 테스트케이스가 한 실행에 들어오기때문에 매반복시 편의점 방문 기록인 visited를 초기화 해주어야합니다.