Memo
로직 설명
•
한 노드에서 다른 노드의 거리가 1000 이하라면 이동할 수 있습니다.
•
인접 행렬로 표현하여 플로이드-와샬을 통해 시작 노드에서 마지막 노드까지 이동할 수 있는지 확인합니다.
Code
제출 날짜
@6/6/2021
import sys
t = int(sys.stdin.readline().strip())
for x in range(t):
n = int(sys.stdin.readline().strip())
li = [[0 for _ in range(n+2)] for _ in range(n+2)]
save = []
for i in range(n+2):
a, b = map(int, sys.stdin.readline().split())
save.append((a,b))
for i in range(n+2):
for j in range(n+2):
if (i == j):
continue
if (abs(save[i][0] - save[j][0]) + abs(save[i][1] - save[j][1]) <= 1000):
li[i][j] = 1
for k in range(n+2):
for i in range(n+2):
for j in range(n+2):
if (i == j):
continue
if li[i][k] and li[k][j]:
li[i][j] = 1
if (li[0][n+1]):
print("happy")
else:
print("sad")
Python
복사