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

• BFS

// https://www.acmicpc.net/problem/9205
// 맥주 마시면서 걸어가기
// BFS
#include<iostream>
#include<cstring>
#include<vector>
#include<tuple>
#include<queue>
using namespace std;
int T, N, x, y, festival_x, festival_y;
bool happy_flag;
void bfs(vector<tuple<int, int, bool>> &v) {

	queue<tuple<int, int, bool>> que;
	while (!que.empty()) que.pop();
	que.push(make_tuple(get<0>(v[0]), get<1>(v[0]), get<2>(v[0])));
	
	while (!que.empty()) {
		int x = get<0>(que.front());
		int y = get<1>(que.front());
		if (x == festival_x && y == festival_y) happy_flag = true;

		for (auto &V : v) {
			if (get<0>(V) == x && get<1>(V) == y) {
				get<2>(V) = true;
			}
		}

		que.pop();

		for (auto V : v) {
			int distance = abs(get<0>(V) - x) + abs(get<1>(V) - y);
			if (distance > 1000 || get<2>(V)) continue;
			que.push(make_tuple(get<0>(V), get<1>(V), get<2>(V)));

		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;

	for (int t = 0; t < T; t++) {
		happy_flag = false;

		cin >> N;
		vector<tuple<int, int, bool>> v;

		cin >> x >> y;
		v.push_back(make_tuple(x, y, false));

		for (int n = 0; n < N; n++) {
			cin >> x >> y;
			v.push_back(make_tuple(x, y, false));
		}
		cin >> festival_x >> festival_y;
		v.push_back(make_tuple(festival_x, festival_y, false));
		bfs(v);

		if (happy_flag) cout << "happy\n";
		else cout << "sad\n";
	}

}

플로이드-와샬로 풀어보려다 어쩌다보니 BFS로..

큰 배열로 선언하고 싶었지만 메모리 초과로 인해 생성할 수 없어서 tuple을 이용

• floyd-warshall

// https://www.acmicpc.net/problem/9205
// 맥주 마시면서 걸어가기
// floyd-warshall
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
int T, N, x, y;
bool arr[102][102];

void floyd_warshall() {
	for (int k = 0; k < N + 2; k++) {
		for (int i = 0; i < N + 2; i++) {
			for (int j = 0; j < N + 2; j++) {
				if (arr[i][k] && arr[k][j]) {
					arr[i][j] = true;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	for (int t = 0; t < T; t++) {
		
		cin >> N;
		vector<pair<int, int>> V;
		for (int n = 0; n < N + 2; n++) {
			cin >> x >> y;
			V.push_back(make_pair(x, y));
		}

		for (int i = 0; i < N + 2; i++) {
			for (int j = 0; j < N + 2; j++) {
				int distance = abs(V[i].first - V[j].first) + abs(V[i].second - V[j].second);
				if (distance > 1000) continue;
				arr[i][j] = true;
			}
		}
		floyd_warshall();
		if (arr[0][N + 1]) cout << "happy\n";
		else cout << "sad\n";
		memset(arr, false, sizeof(arr));
	}

}