백준 경사로 [14890] 파이썬(Python) 코드 + 해설

백준 14890 경사로 문제

 

문제 이해하기

문제 설명

• 지도 크기: N×N ( 2≤N≤100 2≤N≤100 )
• 각 칸에는 그곳의 높이가 적혀 있습니다 ( 1≤높이≤10 1≤높이≤10 ).
• 길: 한 행 또는 한 열 전체를 말하며, 총 2N개의 길이 있습니다.
• 길을 지나갈 수 있으려면 다음 조건을 만족해야 합니다:
  • 길에 속한 모든 칸의 높이가 같거나,
  • 경사로를 놓아서 지나갈 수 있어야 합니다.

경사로 놓는 조건

• 경사로의 특성:
  • 높이: 1
  • 길이: L ( 1 ≤ 𝐿 ≤ 𝑁 1≤L≤N )
  • 경사로의 개수는 충분히 많습니다.
• 경사로를 놓을 수 있는 조건:
  1. 경사로는 낮은 칸에 놓이며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 합니다.
  2. 낮은 칸과 높은 칸의 높이 차이는 1이어야 합니다.
  3. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 합니다.
  4. 이미 경사로를 놓은 곳에는 다시 경사로를 놓을 수 없습니다.
  5. 경사로를 놓다가 범위를 벗어나면 안 됩니다.

 

해결 방법

각 행과 열에 대해 경사로를 놓을 수 있는지 검사하여 지나갈 수 있는 길의 개수를 구합니다.

알고리즘 단계

1. 각 행과 열에 대해 검사:
   • 총 2N개의 길을 검사합니다.
2. 길을 따라가며 높이 변화 확인:
   • 현재 위치와 이전 위치의 높이를 비교합니다.
   • 높이가 같으면 계속 진행합니다.
   • 높이 차이가 1이면 경사로를 놓을 수 있는지 검사합니다.
     • 높이가 증가하는 경우와 감소하는 경우로 나누어 처리합니다.
   • 높이 차이가 1보다 크면 길을 지나갈 수 없습니다.
3. 경사로를 놓을 수 있는지 검사:
   • 높이가 증가하는 경우 (앞의 칸이 낮은 경우):
     • 뒤쪽으로 L개의 칸이 같은 높이인지 확인합니다.
     • 이미 경사로가 설치되어 있는지 확인합니다.
   • 높이가 감소하는 경우 (앞의 칸이 높은 경우):
     • 앞쪽으로 L개의 칸이 같은 높이인지 확인합니다.
     • 이미 경사로가 설치되어 있는지 확인합니다.
4. 경사로 설치 여부 표시:
   • 경사로를 설치한 위치를 표시하여 중복 설치를 방지합니다.
5. 길의 끝까지 검사 완료 시 카운트 증가:
   • 해당 길을 끝까지 문제없이 진행했다면, 지나갈 수 있는 길로 카운트합니다.

 

최종 정답 코드(Python)

N, L = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]

def can_pass(line):
    used = [False] * N  # 경사로 설치 여부
    for i in range(1, N):
        if line[i] == line[i - 1]:
            continue  # 높이가 같으면 계속 진행
        elif line[i] - line[i - 1] == 1:
            # 높이가 1 증가한 경우: 뒤쪽 확인
            for j in range(1, L + 1):
                if i - j < 0 or line[i - 1] != line[i - j] or used[i - j]:
                    return False
                used[i - j] = True
        elif line[i - 1] - line[i] == 1:
            # 높이가 1 감소한 경우: 앞쪽 확인
            for j in range(L):
                if i + j >= N or line[i] != line[i + j] or used[i + j]:
                    return False
                used[i + j] = True
            i += L - 1  # 경사로의 길이만큼 이동
        else:
            # 높이 차이가 1보다 큰 경우
            return False
    return True

result = 0

# 행 검사
for i in range(N):
    if can_pass(grid[i][:]):
        result += 1

# 열 검사
for i in range(N):
    column = [grid[j][i] for j in range(N)]
    if can_pass(column):
        result += 1

print(result)

코드 설명

1. 입력 받기:
   • N, L과 지도의 정보를 입력받습니다.
2. can_pass 함수 정의:
   • 인자로 받은 line이 지나갈 수 있는 길인지 검사합니다.
   • used 리스트를 사용하여 경사로 설치 여부를 기록합니다.
   • line의 각 위치에서 높이 변화를 확인하고, 경사로 설치 가능 여부를 검사합니다.
3. 높이 증가하는 경우 처리:
   • 현재 위치의 높이가 이전 위치보다 1 높을 때:
     • 뒤쪽으로 L개의 칸이 같은 높이인지 확인합니다.
     • 범위를 벗어나거나 높이가 다르거나 이미 경사로가 설치되어 있으면 False를 반환합니다.
     • 경사로를 설치한 위치를 used에 기록합니다.
4. 높이 감소하는 경우 처리:
   • 현재 위치의 높이가 이전 위치보다 1 낮을 때:
     • 앞쪽으로 L개의 칸이 같은 높이인지 확인합니다.
     • 범위를 벗어나거나 높이가 다르거나 이미 경사로가 설치되어 있으면 False를 반환합니다.
     • 경사로를 설치한 위치를 used에 기록합니다.
     • 경사로의 길이만큼 i를 증가시켜 검사 위치를 이동합니다.
5. 행과 열에 대한 검사:
   • 모든 행에 대해 can_pass 함수를 호출하여 지나갈 수 있는지 확인합니다.
   • 모든 열에 대해서도 동일하게 검사합니다.
6. 결과 출력:
   • 지나갈 수 있는 길의 개수를 출력합니다.

박준 14890 경사로 정답