[BOJ] 14890. 경사로(🥇, 구현/시뮬레이션)

문제

풀이

• 모든 행과 열에 대해 탐색이 진행된다
• 높이가 2이상으로 변화하게 되면 탐색을 중단한다
• 경사로는 낮은 칸에 놓아야 하므로 탐색을 진행하다 1칸 높은 칸을 만나게 되면 뒤로 후진해서 경사로를 놓을 수 있는지 확인(back 함수), 1칸 낮은 칸을 만나게 되면 앞으로 나아가면서 경사로를 놓을 수 있는지 확인(fore 함수)
• 경사로는 겹치게 둘 수 없으므로 ramp 를 통해 현재 칸에 경사로가 놓여있는지 확인

import sys
input =sys.stdin.readline

def fore(row, s, n, ramp): # 행, 시작점 값
    for t in range(L):
        next = s+t
        if next>=N: 
            return False
        
        if row[next] != n or ramp[next]:
            return False
        ramp[next] = True
    
    return True


def back(row, s, n, ramp):
    for t in range(1, L+1):
        prev = s-t
        if prev<0:
            return False
        
        if row[prev] != n or ramp[prev]:
            return False
        ramp[prev] = True
    
    return True

def main(arr):
    global ans
    for row in arr:
        t, next = row[0], 1
        ramp = [False]*N
        while next < N:
            if t == row[next]:
                next += 1
                continue

            gap = t-row[next]
            if gap > 1 or gap < -1:
                break

            if gap == -1:
                if not back(row, next, t, ramp):
                    break
            
            elif gap == 1:
                if not fore(row, next, t-1, ramp):
                    break
                next += (L-1)
                
            t = row[next]
        else:
            # print(row)
            ans += 1

N, L = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]
ROTATE_MAP = list(map(list, zip(*MAP))) 
ans = 0

main(MAP)
main(ROTATE_MAP)
print(ans)