Guest User

Untitled

a guest
Aug 15th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. vector<vector<int>> map;
  7. vector<bool> visit;
  8.  
  9. bool dfs(int here, int dist) {
  10. visit[here] = true;
  11. // 현재 노드가 페스티벌 노드의 좌표면 갈수 있기때문에 return true
  12. if (here == dist) return true;
  13.  
  14. for (int i = 0; i < map[here].size(); i++) {
  15. int next = map[here][i];
  16. if (!visit[next])
  17. if (dfs(next, dist)) return true;
  18. }
  19.  
  20. // 반복문과 재귀함수를 수행하면서 dist까지 못가면
  21. // 페스티벌에 못감
  22. return false;
  23. }
  24.  
  25. int main(void) {
  26. int T; cin >> T;
  27.  
  28. for (int t = 0; t < T; t++) {
  29. int n; cin >> n;
  30. vector<pair<int, int>> v;
  31. // n개의 편의점에 상근이의 집과 락페스티벌 좌표를 저장해야하기 때문에
  32. // n + 2만큼 벡터를 생성해줌
  33. map = vector<vector<int>>(n + 2);
  34. visit = vector<bool>(n + 2, false);
  35.  
  36. int in1, in2; cin >> in1 >> in2;
  37. // insert start -> 상근이집
  38. v.push_back(make_pair(in1, in2));
  39.  
  40. // 편의점좌표 입력
  41. for (int i = 0; i < n; i++) {
  42. cin >> in1 >> in2;
  43. v.push_back(make_pair(in1, in2));
  44. }
  45. cin >> in1 >> in2;
  46. // 벡터의 마지막은 페스티벌 좌표
  47. v.push_back(make_pair(in1, in2));
  48.  
  49. // create map
  50. // 입력받은 좌표를 1개의 노드라고 하겠음.
  51. // 50미터 마다 한병씩 마시고, 맥주 한 박스에 20개 들어있어서
  52. // 맥주 한 박스로 최대 1000미터 갈수있음
  53. // 따라서 각 좌표마다 거리가 1000이하 이면 갈수 있기 때문에 연결리스트로 연결해준다.
  54. for (int i = 0; i < v.size(); i++)
  55. for (int j = i + 1; j < v.size(); j++) {
  56. // abs(x좌표차이) + abs(y좌표차이) 해줘야함
  57. // abs(x좌표차이 + y좌표차이) 해주면 오답나옴, x좌표차이와 y좌표 차이의 부호가
  58. // 같으면 상관없지만 다르면 값이 달라짐
  59. if ((abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second)) <= 1000) {
  60. map[i].push_back(j);
  61. map[j].push_back(i);
  62. }
  63. }
  64.  
  65. // 0번이 시작점(상근이집), 종착지는 락페스티벌 좌표
  66. printf("%s\n", (dfs(0, n + 1) ? "happy" : "sad"));
  67. }
  68. }
Add Comment
Please, Sign In to add comment