백준 - 경사로 / Gold 3 / 14890번 / Python

문제 📋

백준 - 경사로

풀이 📝

import sys

N, L = map(int, sys.stdin.readline().split())
rows = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
cols = []

for i in range(N):
    col = []
    for j in range(N):
        col.append(rows[j][i])
    cols.append(col)

roads = rows + cols


def can_pass(N, L, road):
    length = 1  # 같은 높이의 칸 갯수
    i = 1

    while i < N:
        if road[i] == road[i-1]:
            length += 1
            i += 1
            if length > L:  # 최대 L까지만 count
                length = L
            continue

        gap = road[i] - road[i-1]

        if abs(gap) > 1:
            return False

        if gap == 1:  # 오르막
            if length != L:  # 경사로 만들 칸부족.
                return False
            length = 1  # 오르막 끝 지점의 높은 칸은 바로 경사로를 만드는데 활용 가능 -> 1로 초기화.
        elif gap == -1:  # 내리막
            if L <= N-i:  # 경사로를 만들 칸이 충분하다면
                for j in range(i, i + L):  # L개의 칸이 모두 같은 높인지 확인.
                    if road[j] != road[i]:
                        return False
                i = j  # index 확인한 만큼 반영.
                length = 0  # 내리막 끝 지점의 낮은 칸은 경사로에 이미 활용되었기 때문에 -> 0으로 초기화.
            else:
                return False
        i += 1
    return True


def solution(N, L, roads):
    answer = 0

    for road in roads:
        if can_pass(N, L, road):
            answer += 1

    return answer


print(solution(N, L, roads))

2차원 배열에서 각각의 row와 column들을 하나의 길로 봤을 때 지나갈 수 있는 길의 수를 세는 문제이다. 지나갈 수 있는 길은 다음을 만족해야 한다.

1. 모든 칸의 높이가 같다.
2. 높이가 다르지만 경사로를 만들 수 있다.

경사로를 만들기 위해서 length라는 변수를 정의했다.
length는 현재까지 높이가 같은 칸 개수를 의미한다.
다만 경사로를 만드는데 필요한 칸의 수가 L이므로
최대 L까지만 count 했다.

가장 유념해야 할 점은 오르막일 때와 내리막일 때
length 초기화 값을 다르게 해주어야 한다는 것이다.

오르막 끝 지점의 높은 칸은 바로 경사로를 만드는데 활용 가능 -> length = 1 초기화
내리막 끝 지점의 낮은 칸은 경사로에 이미 활용되었기 때문에 -> length = 0 초기화