[BOJ/C++] 9205 맥주 마시면서 걸어가기 : DFS

문제

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

풀이

처음에는 반복문으로 거리 계산하고 다음 목적지까지의 거리가 1000 넘으면 바로 sad를 출력, 문제없이 반복문을 모두 통과했을때는 happy 출력하는 방식으로 접근
=> 다음 목적지에 해당하는 위치가 순서대로 주어진다는 보장이 없음.
즉, 거리가 되는 모든 방향으로 가봐야하므로 그래프 탐색을 이용해야 함

그래프에서 정점만 주어졌다고 생각하고, 거리가 1000 안 넘으면 edge를 만들어 준다고 생각하고 그래프를 만든 후, 그래프 탐색하면 됨

코드

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

using namespace std;

bool check[102];
vector<int> v[102];

void dfs(int node) {
	check[node] = true;

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];

		if (!check[next]) {
			dfs(next);
		}
	}
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		int N;
		int sx, sy, dx, dy;
		vector<pair<int, int>> xy;
		cin >> N;
		cin >> sx >> sy;
		xy.push_back({ sx, sy });
		for (int i = 0; i < N; i++) {
			int tmp_x, tmp_y;
			cin >> tmp_x >> tmp_y;
			xy.push_back({ tmp_x, tmp_y });
		}
		cin >> dx >> dy;
		xy.push_back({ dx, dy });

		for (int i = 0; i < N + 2; i++) {
			for (int j = 0; j < N + 2; j++) {
				if (i != j) {
					int distance = abs(xy[i].first - xy[j].first) + abs(xy[i].second - xy[j].second);
					if (distance <= 1000) {
						v[i].push_back(j);
						v[j].push_back(i);
					}
				}
			}
		}

		dfs(0);

		if (check[N + 1]) {
			cout << "happy" << '\n';
		}
		else {
			cout << "sad" << '\n';
		}

		fill_n(check, 102, false);
		for (int i = 0; i < 102; i++) {
			v[i].clear();
		}
	}

	return 0;
}