BOJ 9205 맥주 마시면서 걸어가기

사용한 알고리즘

플로이드 와샬

알고리즘 설명

시작점(0), 편의점(1 ~ N), 도착지(N+1)로 N+2개의 노드를 만든다.
각 노드 간에 맨해튼 거리가 1000이하면 연결 시킨다.
이후에 플로이드 와샬 알고리즘으로 adj(i)(k) -> adj(k)(j)로 연결 가능 하면 adj(i)(j)도 연결 가능하다.
adj(0)(N+1)의 값으로 시작점과 도착점의 연결 여부를 판단한다.

풀이

// baekjoon 9205 yechan
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;

const int MAX_N=103;
const int LIMIT=1000;

int T, N, x, y;
int adj[MAX_N][MAX_N];
P vertex[MAX_N];

inline int dist(P& a, P& b) {
	return abs(a.first-b.first)+abs(a.second-b.second);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		memset(adj, 0, sizeof(adj));
		scanf("%d", &N);

		// 시작점과 도착점 추가
		N+=2;
		// 입력 받기
		for (int i=0; i<N; i++) {
			scanf("%d%d", &x, &y);
			vertex[i]=P(x,y);
		}

		// 연결 그래프 만들기
		for (int i=0; i<N; i++)
			for (int j=i+1; j<N; j++)
				if (dist(vertex[i], vertex[j]) <= LIMIT)
					adj[i][j] = adj[j][i] = 1;

		// 플로이드 와샬 알고리즘
		for (int k=0; k<N; k++)
			for (int i=0; i<N; i++)
				for (int j=0; j<N; j++)
					adj[i][j] |= adj[i][k] && adj[k][j];

		puts(adj[0][N-1] ? "happy":"sad");
	}
	return 0;
}