문제 링크

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

문제 설명

• N, L, board 주어짐
• 가로 N개, 세로 N개의 길 중에서
• 지나갈수 있는 길의 개수 출력
  • 높이 차이가 1일 경우
  • 길이가 L인 경사로를 놓을 수 있으면 지나갈 수 있음

풀이

• 각 row에 대해서
• 높이가 한 칸 증가
  • 이전 L칸 체크
• 높이가 한 칸 감소
  • 이후 L칸 체크

느낀 점

구현이 상당히 까다로웠다 ㅠ

코드

def possible(line):
    used = [False] * n
    i = 0
    while i+1 < len(line):
        # 높이 같음
        if line[i] == line[i+1]:
            i += 1
        # 높이 1 감소
        elif line[i] == line[i+1] + 1:
            # 범위를 벗어남
            if i+1+l > len(line):
                return False
            # 높이가 다름
            if len(set(line[i+1: i+1+l])) != 1:
                return False
            for j in range(i+1, i+1+l):
                # 경사로 중복
                if used[j]:
                    return False
                used[j] = True
            i += l
        # 높이 1 증가
        elif line[i] + 1 == line[i+1]:
            # 범위를 벗어남
            if i+1-l < 0:
                return False
            # 높이가 다름
            if len(set(line[i+1-l: i+1])) != 1:
                return False
            for j in range(i+1-l ,i+1):
                # 경사로 중복
                if used[j]:
                    return False
                used[j] = True
            i += 1
        else:
            return False
    return True


# init
import sys
read = sys.stdin.readline
n, l = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(n)]
count = 0

# start
for i in range(n):
    row = [board[i][j] for j in range(n)]
    if possible(row):
        count += 1
    col = [board[j][i] for j in range(n)]
    if possible(col):
        count += 1
print(count)