[백준] 14890 경사로 (파이썬 python)

 

 

문제 링크

 

 

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

14890번: 경사로

 

 

문제

 

 

 

 

 

문제 풀이

 

 

def check(line):
    runway = [False for _ in range(n)]
    for i in range(n - 1):
        # 높이가 같을 경우 패스
        if line[i] == line[i + 1]:
            continue
        # 높이차가 1보다 클 경우 그 길은 지나갈 수 없음
        if abs(line[i] - line[i + 1]) > 1:
            return False
        # 높 -> 낮
        if line[i] > line[i + 1]:
            temp = line[i + 1]
            for j in range(i + 1, i + 1 + l):
                if 0 <= j < n:
                    if line[j] != temp:
                        return False
                    # 이미 해당 위치에 경사로 존재
                    if runway[j]:
                        return False
                    runway[j] = True
                else:
                    return False
        # 낮 -> 높
        else:
            temp = line[i]
            for j in range(i, i - l, -1):
                if 0 <= j < n:
                    if line[j] != temp:
                        return False
                    if runway[j]:
                        return False
                    runway[j] = True
                else:
                    return False
    return True


n, l = map(int, input().split())
area = []
for _ in range(n):
    area.append(list(map(int, input().split())))
result = 0

for i in area:
    if check(i):
        result += 1
for i in range(n):
    temp = []
    for j in range(n):
        temp.append(area[j][i])
    if check(temp):
        result += 1

print(result)

 

 

일단 전체 길 중 가로, 세로를 검사할 때 같은 코드를 사용하게 되므로 함수로 작성한다!

문제에서 주어진 길을 지나갈 수 없는 조건들을 하나씩 검사하며

안되는 경우에는 false, 모든 조건을 통과한 경우에는 최종적으로 true를 반환해준다.

 

문제에서 주어진 길을 지날 수 없는 조건은

1) 높이차가 1보다 클 경우

2) 경사로를 넣어야 하는 위치에 이미 경사로가 존재하는 경우

3) 경사로의 길이가 l이 아닌 경우

 

이렇게 세 가지이다.

 

1) 일단 높이가 같을 경우 경사로 없이도 길을 지날 수 있으므로 continue 해준다.

2) 붙어있는 길의 높이가 다른데, 2 이상일 경우 길을 지날 수 없다. 바로 false 반환해준다.

=> 이 두 가지에서 높이 차 0, 2이상은 모두 걸러지고 높이차가 1인 것들만 남는다.

3) 뒤에 나오는 높이가 앞에 나오는 높이보다 1 낮을 경우

낮은 부분부터 l의 길이만큼 같은 높이가 유지되어야 한다. 그 부분을 범위로 잡아주고,

1. 높이가 달라질 경우 l만큼의 경사로의 길이 보장 X => False 반환

2. runway[j]를 true 반환, 이미 경사로 존재 => False 반환

이 두가지를 통과시 경사로에 대한 배열값을 True로 변경해준다.

 

이렇게 l만큼의 길이의 경사로가 존재할 수 있는지 하나씩 검사해주는 것이다

이 때, 경사로가 존재하는 위치가 0이상 n이하여야만 한다. 벗어날 경우 False를 반환해준다.

 

4) 앞에 나오는 높이가 뒤에 나오는 높이보다 1 낮을 경우

3번에서 했던 것을 검사 범위에 대해 step만 -1로 설정하여 반대방향으로 진행되게 한다.