10571. 잔디 깎기 D4

막히는 문제 풀다가 푸는 요령을 좀 안것 같아서 씀.

문제의 핵심을 알아내는 것이 중요하다.. 어찌보면 당연하지만

스스로 테스트케이스 여러가지 만들어내면서 정답이 되는 조건을 생각해서 풀어냄. 작은 경우부터 만족시키면서 점점 더 크게..

# 387 ms
import sys

sys.stdin = open("input2.txt", "r")

def is_safe(now_r,now_c):
    now_e = H[now_r][now_c]
    y_bool = True
    x_bool = True

    # 아래 위
    for i in [1,3]:
        new_y = now_r + dy[i]
        new_x = now_c + dx[i]
        while 0 <= new_y < N and 0 <= new_x < M:
            if H[new_y][new_x] > now_e:
                y_bool = False
                break
            new_y += dy[i]
            new_x += dx[i]
        if not(y_bool): break

    # 왼쪽 오른쪽
    for i in [0,2]:
        new_y = now_r + dy[i]
        new_x = now_c + dx[i]
        while 0 <= new_y < N and 0 <= new_x < M:
            if H[new_y][new_x] > now_e:
                x_bool = False
            new_y += dy[i]
            new_x += dx[i]
        if not(x_bool): break

    return y_bool or x_bool

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, M = map(int, input().split())

    H = [[0] * M for _ in range(N)]
    for i in range(N):
        H[i] = list(map(int, input().split()))

    # print(*H,sep='\n')

    # 왼쪽, 아래, 오른쪽, 위
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]

    result = True
    for r in range(N):
        for c in range(M):
            if not(is_safe(r,c)):
                result = False
        if not(result): break

    result_string = "YES"
    if not(result): result_string = "NO"
    print("#{}".format(test_case), result_string)
    # ///////////////////////////////////////////////////////////////////////////////////

밑에는 핵심 파악 뒤 개선 버전

# 258 ms
import sys

sys.stdin = open("input2.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, M = map(int, input().split())

    Row_max = [0] * N
    H = [[0] * M for _ in range(N)]
    for i in range(N):
        H[i] = list(map(int, input().split()))
        Row_max[i] = max(H[i])

    # print(*H,sep='\n')

    Col_max = [0] * M
    HR = [0 for _ in range(M)]
    for i, c in enumerate(zip(*H)):
        HR[i] = list(c)
        Col_max[i] = max(HR[i])

    # 왼쪽, 아래, 오른쪽, 위
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]

    # print(Row_max,Col_max)
    result = True
    for r in range(N):
        for c in range(M):
            if H[r][c] < Row_max[r] and H[r][c] < Col_max[c]:
                result = False
                break
        if not(result): break

    result_string = "YES"
    if not(result): result_string = "NO"
    print("#{}".format(test_case), result_string)
    # ///////////////////////////////////////////////////////////////////////////////////