[파이썬/Python] 백준 14890번: 경사로

📌 문제 : 백준 14890번

---

📌 문제 탐색하기

N : 지도의 가로세로 크기 ($2 ≤ N ≤ 100$)
L : 경사로의 높이 ($1 ≤ L ≤ N$)
map_info : 각 칸의 높이 ($1 ≤ 높이 ≤ 10$)

문제 풀이

크기가 N×N인 지도의 각 칸에 그 높이가 적혀져 있을 때, 지도에서 지나갈 수 있는 길의 개수를 세는 문제이다.

길 = 한 행 또는 한 열 전부를 의미하며,
길을 지나가기 위해선 길에 있는 모든 칸의 높이가 같아야 한다.

개수가 무한한 경사로를 설치해서 높낮이가 다른 칸을 연결하면서 지나갈 수 있는 길의 개수를 구해야 한다.

⭕️ 경사로 가능한 조건

• 낮은 칸에 놓기 → L개의 연속된 칸에 경사로 바닥 모두 접하기
  • 낮은 칸의 높이 모두 동일 & L칸 연속 필수
• 높은 칸 ←→ 낮은 칸 차이 1

---

❌ 경사로 불가능한 조건

• 경사로 놓은 곳에 또 놓는 경우
  • 낮은 칸의 높이 모두 동일 ❌ 또는 L칸 연속 ❌ 경우
• 높은 칸 ←→ 낮은 칸 차이 1 아닌 경우
• 경사로가 지도 범위 벗어난 경우

→ 위의 조건을 따라 경사로를 설치하는 로직을 구현한다.

지도를 한칸씩 접근하면서 경사로를 설치할 수 있는 곳인지 아닌지를 확인하고 지나갈 수 있는 갯수를 센다.

경사로 설치 가능 여부 확인하기

• 경사로 존재 여부 저장할 리스트 정의
• 현재 칸과 다음 칸의 높이 같은지 확인
  • 같다면 계속 진행
  • 다르다면 경사로 길이만큼 경사로 설치 가능 여부 확인
    • 1칸 차이가 아니면 경사로 불가
      • 1칸 차이이면 경사로 설치
        * 경사로 설치하기
    • L만큼 이동했을 때 범위 내인지 확인
      • 경사로 설치 여부 확인

→ 이를 함수로 구현해 이동할 때마다 호출해준다.

지도의 행, 열 별로 체크

• 행 체크
  • for문으로 바로 행 접근
• 열 체크
  • zip 함수로 열의 요소들을 묶어주어 접근

가능한 시간복잡도

지도 입력 → $O(N^2)$
행, 열 별 경사로 확인 → $O(N * (N * L))$

최종 시간복잡도
$O(N^2 * L))$로,최악의 경우 $O(10^4 + 10^2)$이 되어 제한 시간 2초 내에 연산이 가능하다.

알고리즘 선택

for문으로 각 줄의 경사로 설치 및 가능한 길 탐색

---

📌 코드 설계하기

1. 지나갈 수 있는 길인지 확인하는 함수 구현
   1-1. 경사로 설치 여부 저장한 리스트 정의
   1-2. 해당 줄 확인
   1-2-1. 다음 칸과 높이 같은지 확인
   1-2-2. 높이 차이 확인
   1-2-3. 낮은 곳 -> 높은 곳 경사로
   1-2-4. 높은 곳 -> 낮은 곳 경사로
2. N, L 입력
3. 지도 입력
4. 지나갈 수 있는 길의 개수 초기화
5. 가로 방향 확인
6. 세로 방향 확인
7. 결과 출력

---

📌 시도 회차 수정 사항

1회차

• 자꾸 틀린 출력이 나왔다.
• 낮은 곳에서 높은 곳으로 가는 경사로와 높은 곳에서 낮은 곳으로 가는 경사로의 인덱스 접근 방식을 반대로 작성해서 발생한 문제였다.

---

📌 정답 코드

import sys

input = sys.stdin.readline


# 지나갈 수 있는 길인지 확인하는 함수 구현
def check_road(road):
    # 경사로 설치 여부 저장한 리스트 정의
    slope = [False] * N  # 길이 N만큼 초기화

    # 해당 줄 확인
    for i in range(N - 1):
        # 다음 칸과 높이 같은지 확인
        if road[i] == road[i + 1]:
            continue

        # 높이 차이 확인
        if abs(road[i] - road[i + 1]) > 1:
            return False

        # 낮은 곳 -> 높은 곳 경사로
        if road[i] < road[i + 1]:
            for j in range(L):
                # 범위 내인지 확인
                if i - j < 0 or slope[i - j] or road[i - j] != road[i]:
                    return False
                slope[i - j] = True  # 경사로 설치

        # 높은 곳 -> 낮은 곳 경사로
        elif road[i] > road[i + 1]:
            for j in range(L):
                # 범위 내인지 확인
                if i + 1 + j >= N or slope[i + 1 + j] or road[i + 1 + j] != road[i + 1]:
                    return False
                slope[i + 1 + j] = True  # 경사로 설치

    return True


# N, L 입력
N, L = map(int, input().split())

# 지도 입력
map_info = [list(map(int, input().split())) for _ in range(N)]

# 지나갈 수 있는 길의 개수 초기화
answer = 0

# 가로 방향 확인
for row in map_info:
    if check_road(row):
        answer += 1

# 세로 방향 확인
for col in zip(*map_info):
    if check_road(col):
        answer += 1

# 결과 출력
print(answer)

• 결과