14890_경사로

https://www.acmicpc.net/problem/14890

14890번: 경사로

 

 

 

우선 문제를 쪼개서 가로줄만 확인할 수 있게 생각해보았다. 세로줄은 결국 회전시키면 가로줄과 같기 때문에 두번 탐색하면 될거라 생각했다.

 

문제 케이스에서 3 2 2 1 1 1  해당 라인을 가로줄이라 생각해고 생각해보자.

 

while문을 하나 돌리며 idx 값을 n까지 탐색하면 된다.

 

1. 만약 idx 가 가리키는 값과 다음 값의 차이가 1이 넘어가면 그즉시 종료한다.

2. 만약 다음 숫자가 idx가 가리키는 값보다 작다면 l길이만큼 다음 숫자들을 탐색하고, 경사로가 있다는것과 해당 숫자들이 같음을 확인하고 그렇지 않다면 그즉시 종료한다. 다 통과되면 idx값을 idx + l 값으로 바꾸어준다.

( while 마지막에 idx+1을 해주므로 idx += l-1 로 구현 )

3. 만약 다음 숫자가 idx가 가리키는 값보다 크다면 2번과 반대방향으로 같은방식으로 검사한다. 단 다 통과되어도 idx값을 바꾸어주진 않는다.

 

4. while문을 한바퀴 돌때마다 idx +1을 해준다. 

 

 

가로줄을 체크한 후, 보드를 돌려서 한번더 체크해주는 방향으로 검사했다.

 

import sys
input = sys.stdin.readline

n,l = map(int,input().split())

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

def check():
    global cnt
    for i in range(n):
        idx = 0
        visited = [0] * n
        flg = 1
        while idx<(n-1) and flg:
            num = board[i][idx]
            nnum = board[i][idx+1]
            if abs(num - nnum)>1:
                flg = 0
            elif num > nnum:
                for j in range(1,l+1):
                    if idx+j < n and not visited[idx+j] and board[i][idx+j] == nnum:
                        visited[idx+j]=1
                    else:
                        flg=0
                        break
                else:
                    idx += l - 1
            elif num < nnum:
                for j in range(l):
                    if idx-j >= 0 and not visited[idx-j] and board[i][idx-j] == num:
                        visited[idx-j]=1
                    else:
                        flg = 0
            idx += 1
        if flg:
            cnt +=1
cnt = 0
check()
board = [ [board[j][i] for j in range(n)] for i in range(n)]
check()
print(cnt)