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

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

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

---

입력 제한 조건이 최대 100밖에 들어오지 않습니다. O(n^2)로 대부분 가능한 풀이라는걸 생각하며 문제를 읽었습니다.

(0 ≤ n ≤ 100).

좌표계로 노드의 위치가 들어오기 때문에 처음엔 좌표압축을 해야하나 싶었지만,

필요한 정보는 어떤 한 정점에서 어떤 정점으로 갈 수 있는가? 를 알면 되고

한 정점에서 다른 정점으로 갈 조건은 비용(맥주)를 20병 이하로 먹는 길이 맨해튼 거리가 1000이하면 됩니다.

밑의 코드는 한 정점에서 맨해튼 거리가 1000이하인 정점을 인접노드로 push_back 하는 코드입니다.

 

        for (int i = 0; i < vec.size(); i++) {
               for (int j = 0; j < vec.size(); j++) {
                    if (i == j) continue;
                    int cost;
                    if ((abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) % 50 == 0)
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50;
                    else
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50 + 1;

                    if (cost <= 20) {
                         map[i].push_back(j);
                    }
               }
          }

이후에, DFS를 통해 N+1번정점( 페스티발 )을 방문할 수 있는지만 체크하면 됩니다.

---

전체코드

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

vector<pair<int, int> > vec;

bool visit[103];
vector<int> map[103];

void dfs(int now) {
     visit[now] = true;
     for (int i = 0; i < map[now].size(); i++) {
          if (visit[map[now][i]] == false) {
               dfs(map[now][i]);
          }
     }
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int t; cin >> t;
     while (t--) {
          int n, x, y; cin >> n;
          // 초기화
          for (int i = 0; i <= n + 2; i++) {
               map[i].clear();
               visit[i] = false;
          }
          vec.clear();

          // 입력
          for (int i = 0; i < n+2; i++) {
               int x, y; cin >> x >> y;
               vec.push_back({ x,y });
          }

          // O(n^2)으로 모든정점에서 모든정점까지 비용 update
          for (int i = 0; i < vec.size(); i++) {
               for (int j = 0; j < vec.size(); j++) {
                    if (i == j) continue;
                    int cost;
                    if ((abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) % 50 == 0)
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50;
                    else
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50 + 1;

                    if (cost <= 20) {
                         map[i].push_back(j);
                    }
               }
          }

          // DFS
          // 0번노드 : 집의 위치
          // N+1번노드 : 페스티발의 위치
          dfs(0);
          if (visit[n + 1] == true) cout << "happy\n";
          else cout << "sad\n";
     }
}