[백준] 9205번-(Python 파이썬) - Floyd-Warshall

문제링크 : https://www.acmicpc.net/problem/9205

플로이드 와샬 알고리즘으로 풀었는데 문제에선 최단거리로 이동하라는 말이 없었으니
dfs나 bfs로 풀어도 된다.

문제에서 맨해튼 거리는 첫번째 좌표를 (x1, y1)이라 하고, 두번째 좌표를 (x2, y2)라고 할 때,
|x1 - x2| + |y1 - y2|가 맨해튼 거리이다. 절대값은 함수 abs()를 사용해주면 된다.

맨해튼 거리가 1000이하이면 dp에 도달할 수 있다는 의미로 1을 저장해두고
플로이드 와샬 알고리즘을 이용해 전체 도달가능한 점을 최단거리로 저장해준다.

마지막으로 조건에 맞게 출력해주면 된다.

import sys

input = sys.stdin.readline
inf = sys.maxsize

t = int(input())
for _ in range(t):
    n = int(input())
    graph = []
    for _ in range(n + 2):
        graph.append(list(map(int, input().split())))
    dp = [[inf] * (n + 2) for _ in range(n + 2)]

    for i in range(n + 2):
        for j in range(n + 2):
            if i == j:
                continue
            if abs(graph[i][0] - graph[j][0]) + abs(graph[i][1] - graph[j][1]) <= 1000:
                dp[i][j] = 1
    
    for k in range(n + 2):
        for i in range(n + 2):
            for j in range(n + 2):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j] 
    
    print("happy" if 0 <= dp[0][n+1] < inf else "sad")