[Python] 백준(BOJ): 14890. 경사로

💁🏻  문제

14890번: 경사로

---

🤷🏼‍♀️  문제 설명

한 행 또는 한 열의 한쪽 끝에서 다른 쪽 끝까지 지나가는 것을 길이라 한다.
길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 한다.

단, 경사로를 놓아서 지나가는 길을 만들 수 있다.

• 경사로는 낮은 칸에 놓으며, L개의 연속한 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

L=2인 경우

아래와 같은 경우에는 경사로를 놓을 수 없다. 

• 낮은 칸과 높은 칸의 차이가 1이 아닌 경우
• 경사로를 놓은 곳에 또 경사로를 놓는 경우 (겹치게 놓는 경우)
• 경사로를 바닥과 접하게 놓지 않거나, 기울이게 놓는 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않는 경우 
• 경사로를 놓다가 범위를 벗어나는 경우

 

 

⚙️  풀이

보자마자 구현 문제라는 생각이 들었는데, 경사로를 놓을 수 없는 경우를 어떻게 처리할지 고민하는 부분에서 시간을 많이 쏟았다.

a. 길은 각각의 행, 열에 대하여 존재할 수 있다는 것은 세로 방향, 가로 방향으로 두번 탐색을 진행해야 한다는 의미이다.
    먼저 가로방향(행 연산)으로 길을 계산하고 지도를 90도 돌려서 다시 가로방향(열 연산, 원래 지도에서의 세로방향)으로 수행하면 된다.

b. 경사도를 설치하는 기준을 나눈다.
    → (현재 칸 - 다음 칸)의 값을 기준으로 하여, 각각의 줄에 대해서 아래와 같이 경우의 수를 나누어 연산을 수행하면 된다.

 

import sys

def path(row):
    slope_end = 0       # 경사도가 겹치지 않는 기준 idx
    result = True       # 길이면 True, 아니면 False

    idx = 0
    while idx < N - 1:
        base = row[idx]
        # 높이가 같아 길을 바로 지나갈 수 있는 경우
        if base == row[idx + 1]:
            idx += 1
        # 우측 경사, 내리막 (경사도가 감소하는 방향)
        elif base - row[idx + 1] == 1 and idx + L < N:
            for j in range(idx + 1, idx + L + 1):
                if row[j] != row[idx] - 1:
                    result = False
                    break
            base -= 1
            idx += L
            slope_end = idx + 1
        # 좌측 경사, 오르막 (경사도가 증가하는 방향)
        elif row[idx + 1] - base == 1 and 0 <= idx + 1 - L and (idx + 1) - L >= slope_end:
            for j in range(idx, idx - L, -1):
                if row[j] != row[idx + 1] - 1:
                    result = False
                    break
            base += 1
            idx += 1
        else:
            result = False
            break
    return result


def count_path(arr, N):
    result = 0
    for i in range(N):
        if path(arr[i]):
            result += 1
    return result


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

# 가로 방향 길 탐색
answer += count_path(arr, N)

for i in range(N):
    for j in range(i + 1, N):
        arr[i][j], arr[j][i] = arr[j][i], arr[i][j]

# 지도를 90도 회전하여 세로 방향의 길 탐색
answer += count_path(arr, N)
print(answer)

구현문제는 사전에 경우의 수를 잘 정리해놓고 들어가면 코드를 작성하는 것 자체는 어렵지 않다.
요즘에 구현 문제를 잘 풀지 않고 있었더니, 생각이 정리되는 속도가 너무 느렸다.

구현문제 지문은 마치 국어를 수학 쓰듯이 적어놓는 것 같다.. 문제 이해하는게 진짜 제일 어렵다. 컴공식 언어에 익숙해져야해..