글 읽기 - 이 테스트 케이스가 왜 이답인지 설명해주실분 있나요?

suker80 3년 전 0

정답 코드를 긁어서 테스트 해본 결과

5
3 4 11 8 7 
0 12 17 11 10 
13 19 12 15 6 
10 8 15 17 18 
6 0 15 1 8 
answer= 14

이거의 답이 왜 14인지 궁금합니다

최소값 최대값 경로에는 시작점은 포함 안하는건가요??

제 코드에서는 3 -> 4-> 11-> 17 -> 12 -> 15 -> 17 -> 18 로 지나가서

18 - 3 = 15

최종 답이 15가 나오는데 틀렸다고 뜹니다.

n = int(input())
from collections import deque

graph = [list(map(int, input().split())) for _ in range(n)]

left, right = abs(graph[n - 1][n - 1] - graph[0][0]), 200

mid = (left + right // 2)
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(mid, i=0, j=0):
    min_val = graph[0][0]
    max_val = graph[0][0]
    queue = deque([[i, j, min_val, max_val]])

    visit = [[[0] * n for _ in range(n)] for _ in range(201)]
    visit[min_val][0][0] = True
    while queue:

        y, x, min_val ,max_val= queue.popleft()

        if y == n - 1 and x == n - 1:
            return True

        for dy, dx in direction:
            ny, nx = dy + y, dx + x
            if 0 <= ny < n and 0 <= nx < n and visit[min_val][ny][nx] == 0:

                if max(max_val, graph[ny][nx]) - min(graph[ny][nx], min_val) <= mid:
                    queue.append([ny, nx, min(graph[ny][nx], min_val), max(max_val, graph[ny][nx])])
                    visit[min_val][ny][nx] = 1

    return False


while left < right:

    mid = (left + right) // 2

    flag = bfs(mid)

    if flag:
        right = mid
    else:
        left = mid +1

print(right)

exponential_e 3년 전 1

아래와같이 돌리면 15 - 1 = 14 나오긴 합니다.

3 -> 4 -> 11 -> 8 -> 11 -> 15 -> 12 -> 15 -> 15 -> 1 -> 8

3_    4_    11_    8_    7 
  12     17     11_   10 
 19     12_    15_   6 
  8     15_    17    18 
   0     15_    1_    8_

suker80 3년 전 1

와 이경우를 생각 못하고 있었네요 정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 테스트 케이스가 왜 이답인지 설명해주실분 있나요?

suker80 3년 전 0

exponential_e 3년 전 1

suker80 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말