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

Memo

로직 설명

• 한 노드에서 다른 노드의 거리가 1000 이하라면 이동할 수 있습니다.
• 인접 행렬로 표현하여 플로이드-와샬을 통해 시작 노드에서 마지막 노드까지 이동할 수 있는지 확인합니다.

Code

제출 날짜

2021/06/06

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")