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

문제 풀이

 

생각보다 어려웠고, 알고 나니까 정말 괜찮은 문제라고 생각된다. 나중에 다시 풀어봐야겠다.

 

문제를 요약하면,

자신의 집에서 출발하는데 50미터씩 걸어갈 때마다 맥주를 마셔야 한다.

최대 가지고 다닐 수 있는 맥주의 개수는 20개라 총 1000미터를 다닐 수 있다.

중간에 편의점에 도착하면 맥주의 개수를 다시 20개로 충전할 수 있으므로 중간에 편의점을 만나면 그때부터 다시 1000미터 반경으로 갈 수 있다. 페스티벌에 도착할 수 있다면 해피를 아니면 세드를 표시한다.

 

문제에서는 (x, y) 좌표로 주어진다.

보통 좌표나 연결된 노드가 주어져서 그래프 자료구조를 구현해서 문제를 풀었지만

좌표 형태로 푸는 것은 생소한 경험이라 어려웠다.

 

간단히 생각해보면 집에서 출발했을 때 최대로 갈 수 있는 지점들은 정해져 있다.

맥주의 개수가 20개이므로 최대 1000미터를 갈 수 있다는 말이기 때문에 반경 1000미터의 좌표들을 전부 구해서 해당 지점과 그 지점을 그래프로 표현하면 된다.

 

중요한 점은 어떠한 지점을 도달하게 되면 다시 그 지점에서 다시 반경 1000미터를 옮길 수 있다.

편의점이라면 충전이 되는 것이고, 만약에 그곳이 페스티벌이라면 우리는 답을 찾은 것이기 때문이다.

 

따라서 전체 지점을 확인하면서 반경 1000미터 이내에 있는 지점들끼리 그래프로 연결하고,

그래프 탐색 알고리즘을 돌려서 페스티벌에 도착했는지만 체크하면 해결할 수 있다.

 

소스 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAX = 105;

int n;
vector<int> adj[MAX];
bool visit[MAX];

void dfs(int node)
{
	visit[node] = true;
	for (int i = 0; i < adj[node].size(); i++)
	{
		int next = adj[node][i];
		if (!visit[next])
		{
			dfs(next);
		}
	}
}

// 맨해튼 거리 계산
int getDistance(pair<int, int> a, pair<int, int> b)
{
	return abs(a.first - b.first) + abs(a.second - b.second);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;
	while (tc--)
	{
		for (int i = 0; i < MAX; i++)
		{
			vector<int>().swap(adj[i]);
			visit[i] = false;
		}

		cin >> n;
		vector<pair<int, int> > coord(n + 2);
		for (int i = 0; i < n + 2; i++)
		{
			cin >> coord[i].first >> coord[i].second;
		}

		// 맥주 20개로 갈 수 있는 범위를 추린다.
		for (int i = 0; i < n + 2; i++)
		{
			for (int j = i + 1; j < n + 2; j++)
			{
				if (getDistance(coord[i], coord[j]) <= 1000)
				{
					adj[i].push_back(j);
					adj[j].push_back(i);
				}
			}
		}

		dfs(0);
		// 도착할 수 있는 지점에 도착했다면 그 곳은 방문했다는 것이다.
		if (visit[n + 1])
			cout << "happy\n";
		else
			cout << "sad\n";
	}
	return 0;
}