[Algorithm] Baekjoon 9205번 : 맥주 마시면서 걸어가기

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

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

struct Node
{
    int x;
    int y;
};
 
int t, n, startY, startX, a, b, destY, destX;
vector<Node> convenienceStores;
bool isBreak;
bool visited[101];
 
 
bool checkDistToDest(int startX, int startY, int destX, int destY)
{
    int temp = abs(destX - startX) + abs(destY - startY);
    return  temp <= 1000;
}
 
void DFS(int curX, int curY)
{
    if (checkDistToDest(curX,curY,destX,destY)) // 목적지가 유효거리 안이면
    {
        isBreak = true;
        return;
    }
 
    for (int i = 0; i < convenienceStores.size(); ++i) // 위치들 제각각이라 매번 처음부터 검사.
    {
        int nextX = convenienceStores[i].x;
        int nextY = convenienceStores[i].y;
 
        if (visited[i]) continue; // 방문했던 편의점이면 continue
        if (!checkDistToDest(curX, curY, nextX, nextY)) continue; // 멀면 continue
 
        visited[i] = true;
        DFS(nextX, nextY);
 
        if (isBreak) return;
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        memset(visited, false, sizeof(visited));
        convenienceStores.clear();
        isBreak = false;
 
        cin >> n; // 편의점개수.
        cin >> startX >> startY;
 
        for (int j = 0; j < n; ++j)
        {
            cin >> a >> b;
            convenienceStores.push_back({ a,b });
        }
 
        cin >> destX >> destY;
 
        DFS(startX, startY);
 
        if (isBreak) cout << "happy" << endl;
        else cout << "sad" << endl;
    }
}

현재 출발지에서 목적지까지 갈수있는지 조건검사를 하면서 완전탐색하는 문제이다.

문제 설명에는 맥주개수니 이것저것 써져있지만 크게 의미는 없다.

현재위치에서 목적지를 20병(1000미터) 이내에 못간다면 '반드시' 편의점에 들러야 한다는것만 알면 된다.

한번 방문한 편의점에 대해서는 또 방문할 필요가 없기때문에 수행속도가 느릴 이유는 딱히 없다.