문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오. baekjoon

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

bool is_connectable(pair<int, int> a, pair<int, int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second) <= 1000;
}

string bfs(int n, vector<int> graph[]) {
  queue<int> q;
  vector<bool> is_visited(n + 2);
  q.push(0);
  is_visited[0] = true;
  
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    
    if (node == n + 1) return "happy";

    for (int connected : graph[node]) {
      if (!is_visited[connected]) {
        q.push(connected);
        is_visited[connected] = true;
      }
    }
  }
  return "sad";
}

int main() {
  int tc;
  cin >> tc;

  while (tc--) {
    int n;
    cin >> n;
    
    vector<pair<int, int>> v;
    for (int i = 0; i < n + 2; i++) {
      int x, y;
      cin >> x >> y;
      v.push_back(make_pair(x, y));
    }
    
    vector<int> graph[n + 2];
    for (int i = 0; i < n + 1; i++) {
      for (int j = i + 1; j < n + 2; j++) {
        if (is_connectable(v[i], v[j])) {
          graph[i].push_back(j);
          graph[j].push_back(i);
        }
      }
    }

    cout << bfs(n, graph) << endl;
  }
}

풀이

집, 편의점, 락페 각 점에 대해서 서로간의 거리 차이가 1000 이하라면 happy 상태로 갈 수 있게 된다. 1000 이하의 거리에 대해서만 간선을 그리면 된다. 그려진 그래프에 대해, 집을 시작점으로 해서 락페까지 방문할 수 있는지 체크한다.