[BaekJoon] 백준 9205번 : 맥주 마시면서 걸어가기

9205번 : 맥주 마시면서 걸어가기

처음에 알고리즘을 어떤 걸 사용해야하는지 도저히 감이 안와 힌트를 봤는데 플로이드-워셜 을 사용하라고 되어있었다.

덕분에 다 까먹은 플로이드-워셜 공부 엄청 했다.. 이해도 했지만 ? 계속 풀다보니 BFS 로 풀 수 있었다..

그래프를 만들 때 노드 사이의 거리가 1000 이하 인 경우에만 연결을 해주면 된다.

그리고 BFS 를 수행해서 Festival 좌표로 가는지 안가는지 판별하면 된다.

귀찮아서 미루고 있었던 플로이드-워셜 다시 공부하게 되어서 아주 좋은 경험이었다..

---

import sys
from collections import deque


def calculateDistance(start, end):
	return abs(start[0] - end[0]) + abs(start[1] - end[1])


def makeGraph(coordinates):
	coord_len = len(coordinates)
	graph = {i: [] for i in range(coord_len)}

	for i in range(coord_len):
		for j in range(coord_len):
			if i != j and calculateDistance(coordinates[i], coordinates[j]) <= 1000:
				graph[i].append(j)

	return graph


def BFS(graph, coordinates):
	queue = deque([0])
	visit = {0: 1}

	while queue:
		cur_node = queue.popleft()
		for val in graph[cur_node]:
			if val not in visit:
				if coordinates[val] == coordinates[-1]:
					return 'happy'

				visit[val] = 1
				queue.append(val)
	return 'sad'


for _ in range(int(input())):
	coordinates = []

	for _ in range(int(input()) + 2):
		coord = list(map(int, sys.stdin.readline().rsplit()))
		coordinates.append(coord)

	graph = makeGraph(coordinates)
	print(BFS(graph, coordinates))