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

문제 링크: https://www.acmicpc.net/problem/9205

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

<문제 풀이> 그래프 이론, BFS 알고리즘

 

상근이가 50미터를 가려면 맥주를 한 병 마셔야 합니다. 맥주는 최대 20개까지 가지고 있을 수 있고 편의점에 가면 빈 맥주가 있을 때 리필할 수 있습니다.

 

상근이가 50미터마다 맥주 한 병을 마신다고 생각하지 말고 다음과 같이 바꿔서 생각하면 문제를 쉽게 풀 수 있습니다.

 

상근이는 맥주를 한 번에 다 먹는다. 그러면 상근이는 현재 위치에서 (먹은 맥주 개수 * 50) m만큼 이동할 수 있는 능력치가 생긴다.

편의점을 방문했을 때 남아 있는 이동거리가 950m(빈 병이 하나라도 남은경우)보다 작으면 이동거리가 다시 1000m가 된다.

 

이제 문제를 해결하기 위해서 상근이의집, 페스티벌, 편의점을 그래프의 정점으로 표현합니다.

그다음 상근이 집 정점에서 다른 모든 정점을 탐색하는 기본적인 BFS를 구현하면 됩니다.

이때 방문 가능한 조건은 이전에 방문한 적 없으면서 남아 있는 이동 거리로 다음 정점을 방문할 수 있어야 합니다.

 

 

 

<C++소스코드>

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
 
 
 
class Vertex {
public:
    int x, y;
    int rDist; // 갈 수 있는 남은 거리
    int num; // 편의점 번호
    Vertex(int x, int y, int rDist, int num) : x(x), y(y), rDist(rDist), num(num) {
    }
};
bool visited[103]; //집 1, 페스티벌 102, 편의점 2 to n
int sx, sy;
int ex, ey;
 
vector<Vertex> graph;
 
bool bfs() {
    queue<Vertex> Q;
    Q.push({ sx, sy, 20*50, 0 }); // 처음에 최대 갈 수 있는 거리 1000m 
    visited[0] = true;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto next : graph) { // 모든 정점 확인
            if (visited[next.num])continue; // 이미 방문한 정점은 무시
            int dist = abs(cur.x - next.x) + abs(cur.y - next.y); // 다음 정점까지의 거리 구하기
            if (dist > cur.rDist) continue; // 갈 수 있는 남은 거리로 갈 수 없다면 무시
            int rDist = dist - cur.rDist; // 이동할 거리만큼 차감
            if (rDist <= 950) rDist = 1000; // 정점은 편의점이거나 페스티벌이므로 빈 병이 있으면 무조건 가득 채우면 됨
            Q.push({ next.x, next.y, rDist, next.num }); // 다음 정점으로 이동
            visited[next.num] = true;
            if (next.x == ex && next.y == ey) return true; //만약 페스티벌이면 종료
        }
    }
    return false; // 페스티벌을 갈 수 없는 경우
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int t; cin >> t;
    while (t--) {
        graph.clear();
        fill(visited, visited + 103, false);
        int n; cin >> n;
        cin >> sx >> sy;
        for (int i = 1; i <= n; i++) {
            int x, y; cin >> x >> y;
            graph.push_back({ x, y, 0, i });
 
        }
        cin >> ex >> ey;
        graph.push_back({ ex, ey, 0, 102 });
        if (bfs()) cout << "happy\n";
        else cout << "sad\n";
    }
 
    
    return 0;
 
}