[백준 14890] 경사로 - 파이썬

문제

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

14890번: 경사로

 

 

 

풀이 방법

지나갈 수 있는 길인지 체크할 때, 

• 높이가 같은 경우 : 그냥 넘어감
• 높이가 2 이상 차이 나는 경우 : False 반환
• 왼쪽이 더 높은 경우 : 경사로를 놓을 공간이 있는지 체크 후 경사로 설치
• 오른쪽이 더 높은 경우 : 경사로를 놓을 공간이 있는지 체크 후 경사로 설치

로 나눠서 풀어야 한다. 

 

이 때, 경사로를 설치한 곳에는 중복해서 설치할 수 없기 때문에 bridge 라는 리스트를 만들어 해당 위치에 경사로를 설치했다는 것을 표시해놓아야 한다. 

 

또한 가로를 모두 체크했으면 이제 배열을 90도 회전해 세로를 체크해야 한다. 

 

 

 

코드

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


def check(board):
    bridge = [False for i in range(n)]
    
    for i in range(n-1):
        if board[i] == board[i+1]: #높이가 같은 경우
            continue
        
        if abs(board[i] - board[i+1]) >= 2: #높이가 2이상 차이나는 경우
            return False
        
        if board[i] > board[i+1]: #왼쪽이 더 높은 경우
            for j in range(i+1, i+1+l):
                if 0 <= j < n:
                    if board[j] != board[i+1]:
                        return False
                    if bridge[j] == True:
                        return False
                    bridge[j] = True
                else:
                    return False
                
        else: #오른쪽이 더 높은 경우
            for j in range(i, i-l, -1):
                if 0 <= j < n:
                    if board[j] != board[i]:
                        return False
                    if bridge[j] == True:
                        return False
                    bridge[j] = True
                else:
                    return False
                
    return True
   
    
    
def rotate(n, arr):  #기존 배열 90도로 돌리는 함수
    ret = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = arr[i][j]
            
    return ret
    
    
    
ans = 0
  
for i in floor: #가로로 지나갈 수 있는 길 체크
    if check(i):
        ans += 1

floor = rotate(n, floor)

for i in floor: #세로로 지나갈 수 있는 길 체크
    if check(i):
        ans += 1


print(ans)