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

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 집의 좌표와 n개의 편의점의 좌표와 도착지점의 좌표를 입력받고 

 

이동거리 50m당 맥주한병을 마셔야 하는데 총 보유할 수 있는 맥주는 20병이므로 다음 편의점까지의 거리가 1000m이내에 있다면 계속해서 이동하며 도착지점까지 맥주를 마시면서 갈 수 있는지 여부를 확인하는 문제입니다.

 

좌표사이의 거리는 맨해튼거리인 x좌표의 차이 + y좌표의 차이라고 되어있으므로 그렇게 계산해 주시면 됩니다.

 

저는 bfs를 통해 q의 front에 저장되어 있는 지점과의 차이가 1000m이내에 있는 지점이 있다면 q에 push를 해 주었습니다. 그리고 q의 front에 있는 좌표에서 도착지점까지의 거리가 1000m 이내라면 맥주를 마시면서 갈 수 있으므로 return을 하였습니다.

 

이 문제는 x,y좌표가 음수값이 나올 수 있기 때문에 거리를 x좌표의 차이와 y좌표의 차이를 구하고 나서 절댓값을 붙여주어야 합니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
queue<pair<int, int>> q;
int fest[2];
int store[101][2];
int visited[101];
bool flag = false;

void bfs() {
	
	while(!q.empty()) {
		
		if((abs(fest[0] - q.front().first) ) + (abs(fest[1] - q.front().second) ) <= 1000) {
				flag = true;
				return;
			}
		
		for(int i = 0; i < n; i++) {
			int x = abs(store[i][0] - q.front().first);
			int y = abs(store[i][1] - q.front().second);
			
			if(x+y <= 1000 && !visited[i]) {
				q.push(make_pair(store[i][0], store[i][1]));
				visited[i] = 1;
			}
		}
		q.pop();	
	}
}


int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T;
	int house[2];
	cin >> T;
	
	while(T--) {
		flag = false;
		fill_n(visited, 101 ,0);
		fill(&store[0][0] , &store[100][2], 0);
		
		while(!q.empty())
			q.pop();
		cin >> n >> house[0] >> house[1];
		q.push(make_pair(house[0], house[1]));
		for(int i = 0; i < n; i++)
			cin >> store[i][0] >> store[i][1];
		cin >> fest[0] >> fest[1];
	
	bfs();	
	if(flag)
		cout<<"happy"<<'\n';
	else
		cout<<"sad"<<'\n';
	}

	return 0;
}