백준 9205 : 맥주 마시면서 걸어가기 c++

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

vector<bool> visited;
int startx, starty;
vector<pair<int, int> > v;
pair<int, int> rock;

void bfs(){
	queue<pair<int, int> > q;
	q.push(make_pair(startx, starty));
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		if(abs(x - rock.first)+abs(y - rock.second) <= 1000){
			cout << "happy";
			return;
		}
		else{
			for(int i = 0; i < v.size(); i++){
				if((abs(x - v[i].first) + abs(y - v[i].second)) <= 1000){
					if(!visited[i]){
						visited[i] = true;
						q.push(v[i]);
					}
				}
			}
		}
	}
	cout << "sad";
}


int main(){
	int t;
	cin >> t;
	int n;
	
	int x, y;
	
	for(int i = 0; i < t; i++){
		cin >> n;
		cin >> startx >> starty;
		visited = vector<bool>(n, false);
		v.clear();
		for(int i = 0;  i < n; i++){
			cin >> x >> y;
			v.push_back(make_pair(x, y));
		}
		
		cin >> x >> y;
		rock = make_pair(x, y);
		
		bfs();
		cout << "\n";
	}
		
	return 0;
}

 

알게된 점

최대 1000미터 까지 갈 수 있고, 맨해튼 거리로 측정하니까

x좌표값의 차이, y좌표값의 차이의 절대값의 합이 1000보다 작은 곳을 모두 둘러봅니다.

편의점에 도달하면 편의점에서 맨해튼 거리가 1000보다 작은 곳을 모두 둘러봅니다.

그래서 rock페스티벌 좌표가 있으면 happy 없으면 sad를 출력합니다