BOJ/백준 9205 맥주 마시면서 걸어가기

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

 

해결 아이디어

상근이의 집(시작점), 페스티벌(목적지), 중간에 위치한 편의점(경유지)의 위치가 주어진다

이동할 때, 50m당 맥주 1병을 소비하며, 최대 20병(즉, 1000m) 거리까지 이동이 가능하다

주어진 모든 위치 간의 이동 가능 여부를 판단하고, BFS를 통해 페스티벌까지 도달 가능한지 확인.

 

먼저 그래프 사이에 이동이 이동이 불가능하다고 판단되면 그래프에 값을 넣지 않음

그 후 BFS를 진행해 정답을 찾아냄

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

struct Location{
    int x;
    int y;
};

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

    auto calc = [](Location a, Location b) -> int {
        return abs(a.x - b.x) + abs(a.y - b.y);
    };

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<Location> loc(n + 2);
        for(int i = 0; i < n + 2; i++){
            cin >> loc[i].x >> loc[i].y;
        }
        vector<vector<int>> graph(n + 2);
        for(int i = 0; i < n + 2; i++){
            for(int j = 0; j < n + 2; j++){
                if(calc(loc[i], loc[j]) <= 1000){
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }
        queue<int> q;
        vector<bool> vis(n + 2, false);
        q.push(0);
        vis[0] = true;

        bool ans = false;
        while(!q.empty()){
            int cur = q.front();
            q.pop();

            if(cur == n + 1){
                ans = true;
                break;
            }

            for(int nxt : graph[cur]){
                if(vis[nxt]) continue;
                vis[nxt] = true;
                q.push(nxt);
            }
        }
        cout << (ans ? "happy" : "sad") << "\n";
    }

    return 0;
}

여담

처음에는 문제 설명에 " 직사각형 모양으로 생긴 도시이다." 라는 설명을 듣고 격자형태 처럼 생각해야하나 싶어서 배열을 만들려고 했는데 -32768 ≤ x, y ≤ 32767 이 조건을 보고 입력에 음수도 있고 저대로 2차원 배열을 만들면 터지겠다 싶어서

그래프 형태로 문제를 해결했다