[14890] 경사로

문제

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

풀이

연결된 같은 높이의 칸들을 하나로 묶어 줍니다. 예를들어 한 행이 아래와 같다면

[2, 2, 5, 5, 5, 2, 2]

[높이, 길이(개수)]와 같은 형식으로 묶어줍니다.

[[2, 2], [5, 3], [2, 2]]

이렇게 묶어서 표현한 배열을 이용해서 좌측에서부터 우측까지 통행이 가능한지 for문을 돌려주면 됩니다.

해당 배열을 path라 했을 때 path[i]에 도달할 수 있으려면 path[i]의 높이가 path[i - 1]의 높이보다 1정도 크고, 경사로를 설치 가능해야만 이동할 수 있습니다. 만약 path[i-1][1] (path[i]의 길이) 가 L보다 작다면 false를 반환합니다.

두 번째로 path[i]에 도달할 수 있는 경우는 path[i]의 높이가 path[i - 1]의 높이보다 1정도 작고, 마찬가지로 경사로를 설치 가능해야 이동할 수 있습니다. 똑같이 불가능 하다면 False를 반환하고, 가능하다면 path[i + 1]의 경우를 위해서 path[i]에 경사로를 설치했다는 것을 표시해주기위해 path[i][1]에서 L을 빼주면 됩니다.

마지막으로 path[i]와 path[i - 1]의 높이가 같다면 아무 조치가 필요하지 않고 이동 가능하기 때문에 이 경우는 처리해 줄 필요는 없습니다.

import sys

N, L = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
result = 0

def is_possible(path):
    for i in range(1, len(path)):
        if path[i][0] == path[i-1][0] + 1:  # 현재 높이가 이전 높이보다 높을 때
            if path[i - 1][1] < L: # 경사로 설치 불가
                return False
        elif path[i][0] == path[i-1][0] - 1:  # 현재 높이가 이전 높이보다 낮을 때
            if path[i][1] < L:  # 경사로 설치 불가
                return False
            path[i][1] -= L  # 경사로 설치
        elif path[i][0] != path[i-1][0]:  # 이동 불가
            return False
    else:
        return True

for row in board: # 가로 줄
    path = []
    current_h, size = row[0], 1
    for h in row[1:]:
        if h == current_h:
            size += 1
        else:
            path.append([current_h, size])
            current_h, size = h, 1
    path.append([current_h, size])
    if is_possible(path):
        result += 1
        
for c in range(N): # 세로 줄
    path = []
    current_h, size = board[0][c], 1
    for r in range(1, N):
        if current_h == board[r][c]:
            size += 1
        else:
            path.append([current_h, size])
            size = 1
            current_h = board[r][c]
    path.append([current_h, size])
    if is_possible(path):
        result += 1
print(result)