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

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

14890번: 경사로

Problem

• 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
• 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

조건

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다.

경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

SOL

큰 틀을 구현하는데는 어렵지 않았지만, 경사로를 놓는데에서, 구현할게 많았던 문제였다.

처음에는, 그냥 길이정보만 가지고 구현해줬다가, 경사로를 놓는지점에 땅이 평평한지(경사로를 놓을 수 있는지) 확인하는 과정이 빠져서, 완전 다시 구현을 하는 불상사가 생겨버렸다. 이래서, 조건을 자세히 읽고, 몇개를 끄적여 봐야하는거 같다.. :(

 

왼쪽은 O, 오른쪽은 X

경사로의 유형은 오르막 길,내리막 길 2가지 유형으로 나누어 구현했고, 각각 경사로를 놓을 지점의 땅이 평평한지(높이가 같은지), 범위를 벗어나지 않는지 등등을 검사해주었다.

- 사실, 함수로 따로 빼서 구현했으면 더 편했을거 같긴한다.

import sys
input= sys.stdin.readline

N,L=map(int,input().split())
height=[list(map(int,input().split())) for _ in range(N)]
def row(idx):
    visited=[0 for _ in range(N)]
    # 다리의 높이가 2이상 차이나는 경우
    for i in range(N-1):
        if abs(height[idx][i]-height[idx][i+1]) >1:
            return 0
        #오르막 길
        if height[idx][i]< height[idx][i+1]:
            tmp=[0 for _ in range(N)]
            #뒤에 길이 평평한지 검사
            for k in range(L):
                #범위에서 벗어나는 경우 
                if i-k<0:
                    return 0
                #평평하지 않거나, 경사로가 세워진 곳에 또 경사로를 겹치는 경우
                if height[idx][i] != height[idx][i-k] or visited[i-k] !=0:
                    return 0
                tmp[i-k] = 1
            visited=tmp
        #내리막길
        elif height[idx][i]>height[idx][i+1]:
            tmp=[0 for _ in range(N)]
            for k in range(L):
                if i+k+1>=N:
                    return 0
                #평평하지 않거나, 경사로가 세워진 곳에 또 경사로를 겹치는 경우
                if height[idx][i+1] != height[idx][i+k+1] or visited[i+k+1] !=0:
                    return 0
                tmp[i+k+1] =1
            visited=tmp
    #평평한 경우
    return 1
def col(idx):
    visited=[0 for _ in range(N)]
    # 다리의 높이가 2이상 차이나는 경우
    for i in range(N-1):
        if abs(height[i][idx]-height[i+1][idx]) >1:
            return 0
        #오르막 길
        if height[i][idx]< height[i+1][idx]:
            tmp=[0 for _ in range(N)]
            #뒤에 길이 평평한지 검사
            for k in range(L):
                if i-k<0:
                    return 0
                #평평하지 않거나, 경사로가 세워진 곳에 또 경사로를 겹치는 경우
                if height[i][idx] != height[i-k][idx] or visited[i-k] !=0:
                    return 0
                tmp[i-k] = 1
            visited=tmp
        #내리막길
        elif height[i][idx]>height[i+1][idx]:
            tmp=[0 for _ in range(N)]
            #인덱스 주의! 내리막길의 경우 다음 친구부터 봐야함.
            for k in range(L):
                if i+k+1>=N:
                    return 0
                #평평하지 않거나, 경사로가 세워진 곳에 또 경사로를 겹치는 경우
                if (height[i+1][idx] != height[i+k+1][idx]) or visited[i+k+1] !=0:
                    return 0
                tmp[i+k+1] =1
            visited=tmp
    return 1
total=0
for i in range(N):
    total+=row(i)
    total+=col(i)

print(total)