[boj] 백준 14890 경사로 python 풀이

시키는 대로 하면 되는 구현문제, 조건 분기하는걸 다 정리해 두고 시작해야 중간에 꼬이지 않음.

check함수로 한 줄에 대해서 올라가는 경사로, 내려가는 경사로를 각각 한 번씩 서치함.

두 경우를 서치하고 나면 지나갈 수 있는 길이라고 판별.

 

default 상태는 True(지나갈 수 있는 길)로 두고 지나갈 수 없는 경우를 모두 탐색하여 그때마다 False 리턴.

 

문제)

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

 

코드)

import sys
input = sys.stdin.readline

N, L = map(int,input().split())
MAP = [list(map(int,input().split())) for _ in range(N)]
rotated_MAP = [list(x) for x in zip(*MAP[::-1])]

def check(load : list) -> bool:
    '''
    한 줄에 대해 지나갈 수 있는지 여부 판단
    '''
    visited = set() # 경사로 설치한 곳

    idx = 0
    # 우로 내려가는 경사로
    while idx < N-1:
        if load[idx] - load[idx+1] >= 1:
            # 경사가 1보다 큰지 체크
            if load[idx] - load[idx+1] >1:
                # print('(우)경사가 큼',idx)
                return False
            # 범위 체크
            if not(0<=idx+L<N):
                # print('(우)범위 오류',idx)
                return False
            # 경사로 둘 곳 평평하고 높이가 load[idx+1]인지 체크
            if set(load[idx+1:idx+L+1]) != {load[idx+1]}:
                # print('(우)못둠',idx)
                return False
            visited |= set(range(idx+1, idx+L+1))

        idx += 1

    idx = N-1
    # 좌로 내려가는 경사로
    while idx > 0:
        if load[idx] - load[idx-1] >= 1:
            if load[idx] - load[idx-1] > 1:
                # print('(좌)경사가 큼',idx)
                return False
            # 범위 체크
            if not(0<=idx-L<N):
                # print('(좌)범위 오류',idx)
                return False
            # 경사로 둘 곳 평평하고 높이가 load[idx+1]인지 체크
            if set(load[idx-L:idx]) != {load[idx-1]}:
                # print('(좌)못둠',idx)
                return False
            # 경사로 중복여부 체크
            if len(set(range(idx - L, idx)) | visited) != len(visited) + L:
                # print('(좌)경사로 중복',idx, visited)
                return False

        idx -= 1
    return True


cnt = 0
for i in range(N):
    cnt += check(MAP[i])
    cnt += check(rotated_MAP[i])

print(cnt)