문제

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

접근

맥주 개수 * 50 만큼 갈 수 있고 시작 지점부터 끝 지점까지 도달해야 한다. 맥주가 다 소진되면 갈 수 없으므로 중간에 편의점을 방문하여 맥주를 채워야 한다.

편의점을 방문했을 때 맥주 20개가 채워지므로 20 * 50 = 1000 거리를 한번에 갈 수 있다.

처음에 문제를 보고 거리를 이동할 때 맥주가 소진되므로 최소 거리로 가야겠구나 생각하고 최단경로로 접근하였다.

하지만 문제를 풀면서 두 정점의 x 좌표 거리 + y 좌표 거리가 1000 이하이기만 하면 무조건 도달할 수 있기 때문에 도달 가능성만 확인해주면 된다.

따라서 BFS 알고리즘이라고 확신했고 그 후에는 home을 기준으로 페스티벌 장소까지 도달 가능성을 확인해줬다.

첫 정점(home)에서 락 페스티벌까지 도달할 수 있으면 "happy"를, 도달할 수 없으면 "sad"를 출력해 주면 된다.

처음에 최단 거리라 생각하고 두 정점 사이의 도달 가능성 정보를 graph에 따로 저장해놨지만 BFS인 것을 바로 알았다면 그래프를 만들지 않아도 됐을 것 같다.

소스 코드

#include<bits/stdc++.h>
using namespace std;
typedef struct pair<int, int>p;

void solve() {

	vector<int> graph[103];
	p board[103];

	int N;

	cin >> N;
	for (int i = 0; i <= N + 1; i++) {
		cin >> board[i].first >> board[i].second;
	}

	for (int i = 0; i <= N; i++) {
		for (int j = i + 1; j <= N + 1; j++) {
			if (abs(board[i].first - board[j].first) + abs(board[i].second - board[j].second) <= 1000) {
				graph[i].push_back(j);
				graph[j].push_back(i);
			}
		}
	}

	bool visited[103];
	fill(visited, visited + 103, false);
	queue<int> q;
	q.push(0);
	visited[0] = true;

	while (!q.empty()) {
		int top = q.front();
		q.pop();
		if (top == N + 1) {
			cout << "happy\n";
			return;
		}
		for (int cur : graph[top]) {
			if (!visited[cur]) {
				visited[cur] = true;
				q.push(cur);
			}
		}
	}

	cout << "sad\n";
	return;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while (T--) {
		solve();
	}


	return 0;
}