이번 문제는 BFS를 통해 해결하였다. 문제에 대한 데이터들을 입력받고, grid를 만들어 해당 장애물들을 설치해주었다. 그리고 BFS를 통해 grid를 탐색하며 방문처리와 함께 현재 위치의 높이와 다음 위치의 높이를 비교하며 이동을 시켰고, 현재 체력이 0보다 작아지면 더이상 탐색을 하지 않도록하였다. 만약 도착 위치에 도착했다면 True를 반환하였고, 그렇지 않다면 False를 반환하였다.

Code

from collections import deque
t = int(input())
def move_maze():
    q = deque()
    q.append((sy, sx, f))
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sy][sx] = True
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    while q:
        y, x, cur = q.popleft()
        if cur < 0:
            continue
        if (y, x) == (ey, ex):
            return True
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < h and 0 <= nx < w and not visited[ny][nx]:
                if grid[ny][nx] <= grid[y][x]:
                    visited[ny][nx] = True
                    q.append((ny, nx, cur-1))
                else:
                    if grid[ny][nx] - grid[y][x] <= cur:
                        visited[ny][nx] = True
                        q.append((ny, nx, cur-1))
    return False
for _ in range(t):
    h, w, o, f, sy, sx, ey, ex = map(int, input().split())
    sy, sx, ey, ex = sy-1, sx-1, ey-1, ex-1
    grid = [[0 for _ in range(w)] for _ in range(h)]
    for _ in range(o):
        oy, ox, ol = map(int, input().split())
        grid[oy-1][ox-1] = ol
    if move_maze():
        print("잘했어!!")
    else:
        print("인성 문제있어??")