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

👍 BFS에 대해 궁금하다면?

"깊이 우선 탐색(DFS)"와 "너비 우선 탐색(BFS)" 알고리즘에 대해 알아보자!

💡 맥주 마시면서 걸어가기 info

• 문제 제목 : 맥주 마시면서 걸어가기
• 문제 번호 : 9205
• 난이도 : 골드 V (정답률 : 39.42%)
• 백준 링크 : https://www.acmicpc.net/problem/9205

👀 문제 설명

맥주 한 박스에는 맥주 20병이 있고, 이 박스에는 20개까지의 맥주만 담을 수 있다.
상근이는 페스티벌을 가는 길이고, 집에서 페스티벌까지 갈 때 50m마다 맥주 한 병씩 마실 예정이다.
상근이가 페스티벌까지 맥주가 바닥나지 않게 도착할 수 있는지 출력하는 문제이다.

• 중요 : 각 좌표의 거리는 (x좌표끼리의 차이) + (y좌표끼리의 차이)이다.

예시
집 좌표가 (0, 0)이고, 편의점은 2개의 좌표는 각각 (1000, 0), (1000, 1000)이며, 페스티벌의 좌표는 (2000,1000)일 때

입력

• 테스트 케이스 개수 t
  • 맥주를 파는 편의점의 개수 n
  • 상근이네 집 좌표
    • 편의점 좌표
  • 펜타포트 락 페스티벌 좌표

2 // test case cnt
2 // case1 : 편의점 개수
0 0 // 집 좌표
1000 0 // 편의점 1 좌표
1000 1000 // 편의점 2 좌표
2000 1000 // 페스티벌 좌표
2 // case2
0 0
1000 0
2000 1000
2000 2000

출력 : 상근이가 행복하게 페스티벌에 갈 수 있으면 happy, 맥주가 바닥나서 더 이상 이동할 수 없으면 sad 출력

🔨 해결 방법

쉽게 접근하는 방법 : 편의점 없이 갈 수 있는 거리는 최대 50m * 20병 = 1000m 라는 것!
즉, 현재 좌표와 이동하려는 곳의 거리 차가 1000 이하면 이동할 수 있는 것이다!

🔑 전체 코드

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

struct point
{
    int x; int y;
};

point store[100];   // 편의점 좌표(0 <= 편의점 개수 <= 100)
point festival;     // 페스티벌 좌표
point home;         // 집 좌표
bool visited[100];

int abs(int n) {
    if (n < 0) return -n;
    return n;
}

bool BFS(int n) {
    queue<pair<int, int>> que;
    que.push({home.x, home.y}); // 시작 위치는 "집" (pair는 {}로 입력할 수 있음)

    while (!que.empty()) {
        int x = que.front().first; // pair<first, second>
        int y = que.front().second;
        que.pop();

        if (abs(festival.x - x) + abs(festival.y - y) <= 1000) return true; // 현재 위치에서 페스티벌 위치까지 1000 이하면 가능
        for (int i = 0; i < n; i++) {
            if (visited[i] == 1) {
                // 방문했던 편의점이면 pass
                continue;
            }
            if (abs(store[i].x - x) + abs(store[i].y - y) <= 1000) {        // 편의점까지 이동 가능하면
                visited[i] = 1;                                             // 해당 편의점 방문한 것으로 체크
                que.push({store[i].x, store[i].y});                         // que에 넣어줌
            }
        }
    }
    return false; // while 다 돌았는데도 도착 못했으면 false
}

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);

    int t;  // test case 개수
    cin >> t;

    while(t--) {
        int n; // 맥주를 파는 편의점의 개수
        cin >> n;

        cin >> home.x >> home.y;                // 집 좌표 받기
        for (int i=0; i < n; i++) {
            cin >> store[i].x >> store[i].y;    // 편의점 좌표 받기
        }
        cin >> festival.x >> festival.y;        // 페스티벌 좌표 받기

        bool possible = BFS(n);
        if (possible) cout << "happy\n";
        else cout << "sad\n";

        fill(visited, visited+100, false);
    }

    return 0;
}