[백준] 14890 경사로 with Python

📌 BOJ 14890 경사로

💡 조건

1. 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
   오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다.
   길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

2. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다.
   또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.
   경사로는 높이가 항상 1이며, 길이는 L이다.
   또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
   1. 1.경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
   2. 2.낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
   3. 3.경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

3. 아래와 같은 경우에는 경사로를 놓을 수 없다.
   1. 1.경사로를 놓은 곳에 또 경사로를 놓는 경우
   2. 2.낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
   3. 3.낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
   4. 4.경사로를 놓다가 범위를 벗어나는 경우

4. 지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 문제

5. 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다.
   둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

6. 구현 유형의 문제

🖥 소스 코드

from sys import stdin

n, l = map(int, stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, stdin.readline().split())))
cnt = 0


def check(li):
    sw = [False for _ in range(n)]
    for i in range(n - 1):
        if li[i] == li[i + 1]:
            continue

        if abs(li[i] - li[i + 1]) > 1:
            return False

        if li[i] > li[i + 1]:
            temp = li[i + 1]
            for j in range(i + 1, i + 1 + l):
                if 0 <= j < n:
                    if li[j] != temp:
                        return False

                    if sw[j]:
                        return False

                    sw[j] = True

                else:
                    return False

        else:
            temp = li[i]
            for j in range(i, i - l, -1):
                if 0 <= j < n:
                    if li[j] != temp:
                        return False

                    if sw[j]:
                        return False

                    sw[j] = True

                else:
                    return False
    return True


for i in arr:
    if check(i):
        cnt += 1

for i in range(n):
    temp = []
    for j in range(n):
        temp.append(arr[j][i])
    if check(temp):
        cnt += 1

print(cnt)

🔖 예제 및 실행결과

예제

6 2
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

실행결과

7

⌨️ 문제 풀이

1. 가로, 세로축을 검사해서 내리막길을 설치해서 이동이 가능한 길인지 살펴보는 문제이다.
   문제를 풀이할 때 가장 중요한 것은 경사로를 설치해서 이동이 가능한지를 알아보는 것이다.
   이를 알아보기 위해서 check 라는 함수를 통해 판별한다.

2. 경사로를 설치할 수 있는 조건은 문제에 제시되어 있지만 아래와 같이 다시 정리할 수 있다.
   1. 1.경사로는 입력받은 L개의 연속된 공간에 설치할 수 있다.
   2. 2.낮은 칸과 높은 칸의 높이 차이는 1이어야 경사로를 설치할 수 있다.
   3. 3.같은 높이의 L개의 연속된 칸에 경사로를 설치할 수 있다.
   4. 4.경사로를 놓은 곳에는 다시 경사로를 놓을 수 없다.
   5. 5.경사로를 놓는 곳이 범위를 벗어날 수 없다.

3. (2)번에 기재된 요약된 다섯가지의 조건 중 네번째를 보면 우리는 경사로를 설치한 곳을 표시하여 관리할 배열이 필요하다는 것을 알 수 있다.
   이를 소스코드에서 check 함수 내부에 sw 라는 리스트로 n 개만큼 False 로 초기화하여 만들어두었다.

4. 각 높이를 입력받은 arr을 행기준으로 한줄씩 순회하면서 check 함수를 통해 지나갈 수 있는 길인지 확인한다.

5. arr 리스트의 i 번째 리스트를 순회하면서 현재 순회하고 있는 높이(li[i])가
   그 다음 블럭의 높이(li[i + 1])와 같다면 continue를 해준다.

6. 만약 arr 리스트의 i 번째 리스트를 순회하면서 현재 순회하고 있는 높이 (li[i])와
   그 다음 블럭의 높이(li[i + 1])의 차이가 1보다 크다면 return False

   (2)번 의 2번 조건에 위배

7. (6)번에서도 무사히 False를 return 하지 않았다면, 경사로를 설치한다.
   여기서 현재 순회하고 있는 i 번째 블럭이 i + 1 번째 블럭보다 크다면 i + 1 번째 블럭부터 i + 1 + L 번째 블럭까지 검사해야한다.
   이때 (2)번의 3번 조건에 위배되는지, (2)번의 4번 조건에 위배되는지 검사한다.

8. 또는 현재 순회하고 있는 i 번째 블럭이 i + 1 번째 블럭보다 작다면 i 번째 블럭부터 i - L 번째 블럭까지 검사해야한다.
   이때 (2)번의 3번 조건에 위배되는지, (2)번의 4번 조건에 위배되는지 검사한다.

9. (7)번 혹은 (8)번에서 각각 조건에 위배된다면, return False
   위배되지 않는다면 sw 리스트에 True를 기재하여 경사로 설치 유무를 저장한다.

10. check 함수로부터 반환받은 True or False 값에 따라 cnt 를 1씩 늘려준다.

11. 세로 검사는 따로 temp 리스트를 만들어 각 열을 순회하여 저장한 후, check 함수에 넘겨주고 검사하면 된다.