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

사용언어

Visual studio 2019 C++

생각하기

DFS 알고리즘 사용하기 ‘맨해튼 거리’

맨해튼 거리

두 좌표 사이의 거리를 x좌표간의 거리 + y좌표간의 거리를 나타낸다.

[9205 풀이]

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 100 + 2;
int n;
vector<int> v[MAX];
bool visited[MAX];

int distance(pair<int, int> p1, pair<int, int> p2) {  // 맨해튼의 거리
	return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

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

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];
		if (!visited[next])
			dfs(next);
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < MAX; i++)
			v[i].clear();
		cin >> n;
		vector<pair<int, int>> c;
		for (int i = 0; i < n + 2; i++) {
			int y, x; cin >> y >> x;
			c.push_back(make_pair(y, x));
		}

		for (int i = 0; i < n + 2; i++) {
			for (int j = i + 1; j < n + 2; j++) {
				if (distance(c[i], c[j]) <= 50 * 20) { // c[i]와 c[j]의 차이가 50m * 20병이하라면
					v[i].push_back(j);
					v[j].push_back(i);
				}
			}
		}

		dfs(0); // 0부터 시작함

		if (visited[n + 1]) // n+1 도착지인 festival이 false이 아니면 도착할수 있음
			cout << "happy\n";
		else
			cout << "sad\n";
	}
}

참고풀이: https://jaimemin.tistory.com/709