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

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

14890번: 경사로

import sys

n, l= map(int, sys.stdin.readline().split())
graph = []

for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

def check_garo(i):
    # 가로 라인 확인
    # c는 경사로를 둔 곳이다.
    c = [0 for _ in range(n)]
    for j in range(n-1):
        if abs(graph[i][j] - graph[i][j+1]) > 1:
            return 0
        # 오르막인 경우
        if graph[i][j] < graph[i][j+1]:
            temp = [0 for _ in range(n)]
            for k in range(l):
                # 뒤로 경사로를 둘수 있는지 체크
                if j - k < 0:
                    return 0
                # 평평한지랑 이전에 둔 경사로 있는지 확인
                if graph[i][j] != graph[i][j-k] or c[j-k] != 0:
                    return 0
                temp[j - k] = 1
            c = temp
        # 내리막길
        elif graph[i][j] > graph[i][j+1]:
            temp = [0 for _ in range(n)]
            for k in range(l):
                if j+k+1 >= n:
                    return 0
                if graph[i][j+1] != graph[i][j+1+k] or c[j+k+1] != 0:
                    return 0
                temp[j + k + 1] = 1
            c = temp
    return 1

def check_sero(j):
    c = [0 for _ in range(n)]
    for i in range(n-1):
        if abs(graph[i][j]- graph[i+1][j]) > 1:
            return 0
        if graph[i][j]< graph[i+1][j]:
            temp = [0 for _ in range(n)]
            for k in range(l):
                if i - k < 0:
                    return 0
                if graph[i][j] != graph[i-k][j] or c[i-k] !=0:
                    return 0
                temp[i-k] = 1
            c =temp
        elif graph[i][j] > graph[i + 1][j]:
            temp = [0 for _ in range(n)]
            for k in range(l):
                if i + k + 1 >= n:
                    return 0
                if graph[i + 1][j] != graph[i + k + 1][j] or c[i + k + 1] != 0:
                    return 0
                temp[i + k + 1] = 1
            c = temp

    return 1
ans = 0

for i in range(n):

    ans += check_garo(i)
    ans += check_sero(i)

print(ans)

진짜 도저히 생각이 안나서 

아래의 블로그를 참고하고 풀었습니다.

https://chldkato.tistory.com/154

백준 14890 경사로 (파이썬)

로직에 대한 설명은 코드에 같이 적어두었습니다.

 

이 문제를 풀며 배운점

처음에는 모든 그래프를 for 문을 돌면서 풀려했는데

이렇게 위와 같은 방법으로 작게 나누어서 푸는 법도 있다는걸

다시 깨달았다

한번에 하기 어려운 문제는 작게 나누어서 접근해보자!