백준[9205] - 맥주 마시면서 걷기

문제

백준 9205 문제 보기

접근 방법

문제를 이해하기 힘들었다. 하지만 결론은 20병의 맥주를 다 마시기 전에 다른 편의점을 도착할 수 있는지의 여부, 그리고 도착지에 갈 수 있는지를 확인하면 된다.

• 맥주 20개로 갈 수 있는 거리는 1000이다. 따라서 출발지로 부터 1000이내 편의점 또는 목적지가 있는지 검사한다.

코드

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int T, N;
string ans;
vector<pair<int, int>> dist;
int visited[105];

// 거리 측정
bool get_distance(int x1, int y1, int x2, int y2) {
    int diff = abs(x1 - x2) + abs(y1 - y2);
    return (diff <= 1000)? true : false;
}

void dfs(int idx) {
    if(idx == N + 1) {
        ans = "happy";
        return;
    }

    for(int i = 1; i < N + 2; i ++) {
        if(!visited[i]) {
            // 거리 확인
            if(get_distance(dist[idx].first, dist[idx].second, dist[i].first, dist[i].second)) {
                visited[i] = 1;
                // 이동
                dfs(i);
            }
        }
    }
}

int main() {
    cin >> T;
    for(int t = 1; t <= T; t ++) {
        cin >> N;
        ans = "sad";
        dist.clear();
        memset(visited, 0, sizeof(visited));

        for(int i = 0; i < N + 2; i ++) {
            int num1, num2;
            cin >> num1 >> num2;
            dist.push_back({num1, num2});
        }
        dfs(0);
        cout << ans << endl;
    }
    return 0;
}