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

맥주 마시면서 걸어가기 (백준 Gold 5)

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

시작점에서 중간점을 거쳐 목표점까지
맨해튼 거리로서 1000 미터 제한을 가지고
갈 수 있는지를 판별하는 문제

풀이 방법

문제가 다소 헷갈릴 순 있으나
한번에 갈 수 있는 거리가 1000까지라 요약할 수 있다

이후 현재 위치에서 ‘종점’을 갈 수 있는지를 체크하며
BFS 탐색을 진행하면 된다
(다만 갈 수 있는 최대 거리는 1000이기에 그 부분을 유념해야 한다)

제출 코드

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<math.h>

using namespace std;

struct pos
{
	int y, x;
};

inline int Mahatten(const pos& a, const pos& b)
{
	return abs(a.y - b.y) + abs(a.x - b.x);
}

inline bool CanReach(const pos& a, const pos& b)
{
	return Mahatten(a, b) <= 1000 ? true : false;
}

bool bfs(const pos& start, const pos& target, const vector<pos>& cVec)
{
	int cSize = cVec.size();

	if (cSize == 0)
	{
		return CanReach(start,target);
	}

	queue<pos> q;
	q.push(start);

	vector<bool> visit(cSize, false);

	while (q.empty() == false)
	{
		pos now = q.front();
		q.pop();

		if (CanReach(now, target))
			return true;

		for (int i = 0; i < cSize; i++)
		{
			if (visit[i] == false &&
				CanReach(now, cVec[i]))
			{
				visit[i] = true;
				q.push(cVec[i]);
			}
		}

	}

	return false;
}

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

	while (t > 0)
	{
		int cNum;
		cin >> cNum;

		pos start, target;
		cin >> start.x >> start.y;
		vector<pos> cVec;
		for (int i = 0; i < cNum; i++)
		{
			pos t;
			cin >> t.x >> t.y;
			cVec.push_back(t);
		}

		cin >> target.x >> target.y;

		if (bfs(start, target, cVec))
		{
			cout << "happy" << '\n';
		}
		else
		{
			cout << "sad" << '\n';
		}

		t--;
	}


	return 0;
}

결과