(Python) 백준 14890번 : 경사로

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

14890번: 경사로

---

 

(Python) 백준 14890번 : 경사로¶

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

• 알고리즘 분류
  • 시뮬레이션

---

In [1]:

def row_fc(x): # board 에서 특정 행,row(=x)
    array = set() # 경사로 업데이트 해줘야할 좌표들 모음
    for y in range(N-1):
        ## 현재 원소와 그 다음 원소값이 동일
        if board[x][y] == board[x][y+1]: continue
        ## 다음 원소가 1 더 크다.
        if board[x][y] + 1 == board[x][y+1]:
            if not(y+1-L >= 0): return False # 왼쪽 공간이 있는지 확인
            for i in range(L):
                if not(board[x][y] == board[x][y-i]): return False # 같은 높이인지 확인
                if row_board[x][y-i]: return False # 기존에 경사로가 있었는지 확인
                if (x, y-i) in array: return False # 기존 경사로 확인 2
            for i in range(L):
                array.add((x, y-i))
        ## 다음 원소가 1 더 작다.
        if board[x][y] - 1 == board[x][y+1]:
            if not(y+L < N): return False # 오른쪽에 공간이 있는지 확인
            for i in range(L):
                if not(board[x][y+1] == board[x][y+1+i]): return False # 같은 높이인지 확인
                if row_board[x][y+1+i]: return False # 기존에 경사로가 있었는지 확인
                if (x, y+1+i) in array: return False # 기존 경사로 확인 2
            for i in range(L):
                array.add((x, y+1+i))
        ## 다음 원소와의 차이가 2이상
        if abs(board[x][y] - board[x][y+1]) >= 2: return False
    for ax, ay in array:
        row_board[ax][ay] = True  # row_board 에서 경사로 놓은 지점을 True 변환
    return True

In [2]:

def col_fc(y): # board 에서 특정 열,col(=y)
    array = set()
    for x in range(N-1):
        ## 현재 원소와 그 다음 원소값이 동일
        if board[x][y] == board[x+1][y]: continue
        ## 다음 원소가 1 더 크다.
        if board[x][y] + 1 == board[x+1][y]:
            if not(x+1-L >= 0): return False # 위쪽 공간이 있는지 확인
            for i in range(L):
                if not(board[x][y] == board[x-i][y]): return False # 같은 높이인지 확인
                if col_board[x-i][y]: return False # 기존에 경사로가 있었는지 확인
                if (x-i, y) in array: return False # 기존 경사로 확인 2
            for i in range(L):
                array.add((x-i, y))
        ## 다음 원소가 1 더 작다.
        if board[x][y] - 1 == board[x+1][y]:
            if not(x+L < N): return False # 오른쪽에 공간이 있는지 확인
            for i in range(L):
                if not(board[x+1][y] == board[x+1+i][y]): return False # 같은 높이인지 확인
                if col_board[x+1+i][y]: return False # 기존에 경사로가 있었는지 확인
                if (x+1+i, y) in array: return False # 기존 경사로 확인 2
            for i in range(L):
                array.add((x+1+i, y))
        ## 다음 원소와의 차이가 2이상
        if abs(board[x][y] - board[x+1][y]) >= 2: return False
        for ax, ay in array:
            col_board[ax][ay] = True
    return True

In [3]:

if __name__ == '__main__':
    ## 입력
    N, L = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    
    row_board = [[False]*N for _ in range(N)]
    col_board = [[False]*N for _ in range(N)]

    cnt = 0
    for cx in range(N):
        if row_fc(cx): cnt = cnt + 1
    for cy in range(N):
        if col_fc(cy): cnt = cnt + 1
    
    print(cnt)

6 2
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2
7