[백준] 14890 경사로 (파이썬)

골드 Ⅲ

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

14890번: 경사로

 

📄 문제

• 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그곳의 높이가 적혀 있다.
• 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다.
• 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른 쪽 끝까지 지나가는 것이다.
• 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다.
• 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.
• 경사로는 높이가 항상 1이며, 길이는 L이다.

 

경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야 한다.

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

 

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

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

 

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

 

 

---

💡 아이디어

• 구현 문제이다.
• 경사로의 조건을 따져가며 지나갈 수 있는 길인지 확인해 주면 된다.
• 각 행과 각 열이 지나갈 수 있는 길 인지를 확인한다.
• 열을 쉽게 확인하기 위해 zip(*iterable) 함수를 이용하여 전치행렬을 만들어준다.
  • 전치행렬이란? 임의의 행렬 A가 주어졌을 때, 그 행렬의 행과 열을 교환하여 얻는 행렬이다.
  • zip(*iterable) 함수는 동일한 개수로 이루어진 자료형을 묶어주는 역할을 하는 함수이다.
  • *iterable 은 반복 가능한 자료형 여러 개를 입력할 수 있다는 의미이다.

 

• 지나갈 수 있는 길인지 확인하는 함수를 만들어 준다.
• 현재 길의 높이와 다음 길의 높이 차이를 구분하여 탐색한다.
• 길의 높이가 같을 경우 문제없이 지나갈 수 있다.
  1. 평지 일 때 (현재 높이와 다음 높이가 같을 때)

• 길의 높이가 다를 경우에 문제가 발생하며 경사로 조건을 확인해야 한다.
  1. 내리막일 때 (다음 높이가 현재  높이보다 1 작을 때)
  2. 오르막일 때 (다음 높이가 현재  높이보다 1 클 때)
  3. 높이가 2이상 차이 날 때

• 내리막일 때는 인덱스를 L만큼 건너뛸 수 있으므로 while문을 활용하여 탐색한다.
• 함수가 False를 반환하지 않고 while문을 통과할 경우 지날 수 있는 길이므로 True를 반환한다.
• 원래 행렬과 전치행렬의 각 행을 탐색하며 지나갈 수 있는 길인지 확인한다.
• True를 반환하는 행과 열의 개수를 센다.

 

1. 평지 일 때 (현재 높이와 다음 높이가 같을 때)

• 경사로를 놓을 때 평지가 필요하므로 평지를 지날 때마다 same변수에 평지의 개수를 세어준다.

 

2. 내리막일 때 (현재 높이보다 1 작을 때)

• 현재 길이 이후 칸부터 경사로가 놓일 L개의 연속된 칸이 존재하는지 확인한다.
• L개의 연속된 칸이 높이가 같은 평지인지 확인한다.
• L개의 연속된 칸이 존재하지 않거나 평지가 아니면 경사로를 놓을 수 없기 때문에 False를 반환한다.
• 1,2번 조건을 통과하면 경사로가 놓인 마지막 칸의 인덱스(현재인덱스+L)로  위치를 바꿔준다.
• 경사로가 놓인 마지막 칸 위치로 이동되므로 same(평지의 개수)는 0이 된다.

 

3. 오르막일 때 (현재 높이보다 1 클 때)

• 1 높은 칸을 만나기 직전까지 지나온 길에 L개의 칸이 연속된 칸이 존재하는지 확인한다.
• 평지를 지날 때마다 개수를 세었기 때문에 same으로 확인하면 된다.
• 평지의 개수가 L보다 작을 경우 경사로를 놓을 수 없기 때문에 False를 반환한다.
• 경사로는 놓을 수 있는 경우 경사로를 지나 올라온 칸의 위치(현재 인덱스+1)로 바꿔준다.
• 1칸 올라온 위치가 되므로 same(평지의 개수)는 1이 된다.

 

4. 높이가 2 이상 차이 날 때

• 경사로를 놓을 수 없으므로 False를 반환한다.

 

📝 문제 풀이 (Code)

import sys
input = sys.stdin.readline

# 해당 행의 길이 지나갈 수 있는 길인지 판별하는 함수
def way(i, matrix):
    j = 0
    # 평지 개수
    same = 1
    while j < n-1:
        if matrix[i][j] == matrix[i][j+1]:
            # 평지일 때
            j += 1
            same += 1
        elif matrix[i][j] - 1 == matrix[i][j+1]:
             # 내리막길일 때
            for k in range(1,l+1):
                if j+l < n and matrix[i][j] - 1 == matrix[i][j+k]:
                    pass
                else:
                    return False
            j += l
            same = 0

        elif matrix[i][j] + 1 == matrix[i][j+1]:
            # 오르막길일 때
            if same < l:
                return False
            same = 1
            j += 1
        else:
            # 높이가 2 이상 차이 날 때
            return False

    return True


n, l = map(int,input().split())
height = [list(map(int,input().split())) for _ in range(n)]
# 전치행렬
colHeight = list(zip(*height))
cnt = 0
# 전치행렬을 이용하여 행과 열 탐색
for i in range(n):
    if way(i, height):
        cnt += 1
    if way(i, colHeight):
        cnt += 1

print(cnt)