python으로 푸는 백준 14890. 경사로

백준 14890. 경사로

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같거나, 높이 1짜리 경사로를 놓고 지나갈 수 있으면 된다.

지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보는 코드를 짜야한다.

백준에서 푼 문제 리스트 보러가기

백준에서 문제 보기

github에서 코드 보기

문제 조건

경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.

경사로를 높을 수 있는 높이의 차는 1이다.

경사로를 높을 수 있는 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

문제에서 제시한 경사로를 높을 수 없는 경우를 잘 따져서 수를 세어야 한다.

단, 내려가는 모양의 경사로와 올라가는 모양의 경사로가 하트 가운데 모양처럼 평지가 없이 서로 붙여두는건 가능하다. (문제에서 제시한 조건에 위배되지 않음)

문제 풀이

경사로의 모양은 내려가는 모양의 경사로, 올라가는 모양의 경사로 2가지이다.

경사로를 둘 수 있는지 여부는 어떻게 체크할까.

내려가는 모양의 경사로는, 경사로를 놓기 시작하는 시점부터 L개 만큼 평지가 유지되어야 한다. 올라가는 모양의 경사로를 측정하기 위해서, 매 칸마다 이전 칸과의 높이를 비교하여 몇개의 칸이 같은 높이를 유지하고 있었는지 수를 세고 있어야 한다. 

올라가는 모양의 경사로는, 경사로를 놓기 시작하는 시점에서 L개 만큼 전까지 평지가 유지되고 있었어야 한다.

처음에는 현재 칸과 다음칸을 비교하는 코드를 짰으나, 그렇게 했더니 다음과 같이 맨 마지막 부분에 경사로를 놓을 수도 없는 경우가 나오는데 코드가 미숙하여 아래의 경우를 실패 케이스로 구분하지 못했다. 그래서 그냥 속 편하게 이미 지나온 지점과 현재의 지점의 높이를 비교하는 코드로 다시 짰다.

문제에서 제시하는 4가지 테스트 케이스를 모두 통과하면, 문제는 모두 통과할 수 있다. 

보니까 대다수의 다른 사람보다 빠르게 테스트 케이스를 통과한다. 

가로, 세로의 길은 어떻게 체크할까

나는 굳이 세로의 길은 체크하는 코드를 짜지 않았다. 

가로의 길만 체크할 수 있는 함수를 만들어두곤, 파이썬의 zip 코드를 사용해서 세로의 길들을 배열로 가지는 2차원 배열을 다시 생성해서 짜놓은 함수에 넣어주었다.

하나의 2차원 배열을 활용하는 것보다는 메모리를 많이 사용하지만, 대신 코드를 짜는 시간을 줄일 수 있어서 이 방법을 선택하였다. 

파이썬 코드

import sys
input = sys.stdin.readline
 
def solve(n, l, board):
    zip_board = list(map(list, list(zip(*board))))
    count1 = counting(n, l, zip_board)
    count2 = counting(n, l, board)
    return count1 + count2
 
def counting(n, l, board):
    count = 0
    for i in range(n):
        continued = 0
        prev_height = -1
        cur_height = -1
        checked = False
        
        for j in range(n):
            cur_height = board[i][j]
 
            # 현재의 칸과 동일한 높이의 수
            if 0 <= prev_height and prev_height != cur_height:
 
                # 경사로를 놓을 수 있는지 체크하고 있는 경우
                if checked:
                    if l == continued:
                        continued = 1
                        checked = False
                        continue
                    else:
                        break
 
                # 높이의 차
                gap = prev_height - cur_height
 
                # 높이 차이가 2 이상인 경우 (경사로 x)
                if abs(gap) != 1:
                    break
 
                # case2, 올라가는 모양의 경사로
                if gap < 0:
                    if l <= continued:
                        # 현재부터 다시 같은 높이의 칸을 센다
                        continued = 1
                    else:
                        break
                # case1, 내려가는 모양의 경사로
                else:
                    continued = 1
                    checked = True
                    if l == continued:
                        continued = 0
                        checked = False
            else:
                continued += 1
                if checked:
                    if l == continued:
                        continued = 0
                        checked = False
 
            # 현재의 높이를 이전 높이로 업데이트
            prev_height = cur_height
        else:
            # 경사로를 놓을 수 있는지 체크 중이 아닌 경우만 길로 체크
            if not checked:
                count += 1
    return count
 
 
 
if __name__ == "__main__":
    n, l = map(int, input().strip().split())
    board = []
    for i in range(n):
        board.append(list(map(int, input().strip().split())))
    print(solve(n, l, board))

#백준 14890 경사로 #14890 경사로 python #14890 경사로 파이썬 #14890 경사로 백준