맥주 마시면서 걸어가기


작성일 : 2017-01-11 21:15:15
조회수 : 1058



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


시작지점에서 임의의 편의점을 경유하여 맥주가 비지 않게 유지하며 도착지점에 도달할 수 있는지를 파악하는 문제입니다.


중요한 것은 어느 경로를 지나가며 도착하는지가 아니라, 도착할 수 있는지, 없는지에 대한 정보 뿐이므로 어느 한 편의점에 도착했다고 하면, 그 편의점은 다른 경로로 도착하는 경우를 파악할 필요가 없게 됩니다.


따라서 BFS 알고리즘을 이용하여, 시작지점에서 갈 수 있는 편의점 목록을 구하고, 그 편의점부터 도착지점에 도착할 수 있는지를 체크하면 되며, 한번 큐에 들어온 편의점은 별도의 boolean 배열 체크를 통해 중복해서 넣어주지 않아도 됩니다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
typedef long long ll;
using namespace std;

class Node
{
public:
    int x, y, dist;
    Node() {}
    Node(int x, int y) : x(x), y(y) { dist = x + y; }
    bool operator <(const Node &n)
    {
        return dist < n.dist;
    }
};
int n, sx, sy, px, py, ex, ey;
bool calc(Node a, Node b)
{
    return (abs(a.x - b.x) + abs(a.y - b.y)) <= 1000;
}
int main()
{
    ios::sync_with_stdio(false);

    int T;

    cin >> T;
    while (T--)
    {
        
        bool f = false, visited[101] = { 0 };
        vector<Node> w;

        cin >> n >> sx >> sy;
        for (int i = 0; i < n; i++)
        {
            cin >> px >> py;
            w.push_back({ px,py });
        }
        cin >> ex >> ey;
        Node s(sx,sy), e(ex,ey);
        if (calc(s, e)) f = true;
        queue<int> q;
        for (int i = 0; !f && i < n; i++)
        {
            if (calc(s,w[i]))
            {
                visited[i] = true;
                q.push(i);
            }
        }
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
            
            if (calc(w[now], e))
            {
                f = true;
                break;
            }
            for (int i = 0; i < n; i++)
            {
                if (!visited[i] && calc(w[now], w[i]))
                {
                    visited[i] = true;
                    q.push(i);
                }
            }
        }
        cout << (f ? "happy" : "sad") << "\n";
    }
}

맥주 마시면서 걸어가기 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글