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

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/9205

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

---

2. 풀이 과정

• 문제 해결의 흐름
  1. 맥주가 20개 있는 상태(full)에서는 거리가 1000미터 이하인 곳까지 도착할 수 있다. 
  2.  편의점이 왜 n개가 주어졌을까...?? 사실 페스티벌에서 가장 가까운 편의점을 bfs로 찾아 그 편의점과 페스티벌 사이의 거리가 1000 미터 이하인지 확인하는 문제 아닐까?
• 나의 코드

//
// Created by 태윤맥북 on 4/15/24.
// 1. 맥주가 20개(full) 있는 상태에서 현재 있는 거리에서 페스티벌까지 거리가 1000 이하면 무조건 도착 가능
// 2. 편의점이 왜 n개가 주어졌을까....?? 사실 페스티벌에서 제일 가까운 편의점을 bfs로 찾아서 그 편의점과 페스티벌 사이의 거리가 1000 이하인지 구하는 문제 아닐까?
//

#include <iostream>
#include <queue>
#include <cmath>    // abs 함수 사용하려고
using namespace std;

// 좌표 구조체 생성
struct coordinate {
    int x;
    int y;
};

bool cnv_visited[101]; // 편의점 방문
coordinate home;
coordinate fest;

// bfs 구현
bool bfs(coordinate conv[100], int n) {
    queue<coordinate> q;
    q.push(home);   // 첫 시작은 집

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();

        if (abs(fest.x - x) + abs(fest.y - y) <= 1000) return true;

        // 현재 위치에서 갈 수 있는 편의점을 전부 큐에 넣음
        for (int i = 0; i < n; i++) {
            if (!cnv_visited[i] && ((abs(conv[i].x - x) + (abs(conv[i].y - y))) <= 1000 )) {  // 아직 방문하지 않았음
                q.push(conv[i]);
                cnv_visited[i] = true; // 방문 처리
            }
        }
    }

    return false;   // 락페 못 갈 경우
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int n;  // 편의점 개수

        cin >> n;
        cin >> home.x >> home.y;    // 집 좌표 입력 받기
        coordinate conv[101];
        for (int j = 0; j < n; j++) {   // 편의점 좌표 입력 받기
            cin >> conv[j].x >> conv[j].y;
        }
        cin >> fest.x >> fest.y;    // 페스티벌 좌표 입력 받기
        fill_n(cnv_visited, n, false);  // 편의점 방문 여부 전부 false로 초기화시키기

        if (bfs(conv, n)) cout << "happy" << endl;
        else cout << "sad" << endl;
    }

    return 0;
}

• 이 문제를 통해 얻어 갈 수 있는 것들
  • 좌표값같은 경우 구조체 변수를 통해 쉽게 저장할 수 있다.
  • ⭐️ 음수 - 음수의 경우 결과가 -이다. 음수끼리의 차이까지 고려하여 두 수의 차이를 구하고 싶다면 cmath 헤더 파일의 abs 함수를 이용해보자.
  • ⭐️ fiil_n 메소드를 통해 특정 배열을 특정 값으로 초기화시킬 수 있다. 첫번째 인자의 값은 배열의 초기값 주소이고, 두번째 인자는 배열의 크기, 세번째 인자의 경우 초기화하려는 값이다.  

---

3. 후기 

 fill_n 메소드와 abs 메소드를 활용한 문제! 생각보다 쉽게 풀렸다.