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

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 14890번: 경사로

1. 문제

1. 크기가 N*N인 지도의 각 칸에는 높이가 적혀있다.
2. 지도의 길은 N개의 행과 N개의 열로 총 2N개이다.
3. 길을 지나기 위해서는 길에 속한 모든 칸의 높이가 같거나 경사로를 놓아야 한다.
4. 경사로 조건은 다음과 같다.
   1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
   2. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
   3. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어야 한다.
5. 유효한 길의 개수를 출력한다.

2. 풀이

시뮬레이션을 이용한 문제 풀이

1. 경사로는 반드시 1 -> 앞 뒤 차이가 2 이상이면 불가
2. 길의 확인 방향은 계산하기 쉽게 행은 동쪽, 열은 남쪽
   • 오르막은 이전에 연속된 낮은 칸의 유무를 바로 확인
   • 내리막은 이후에 연속된 낮은 칸의 유무를 순차적으로 확인

3. 코드

N, L = map(int ,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
ret = 0
def solution():
    global ret
    def slope(i, d):
        global ret
        cnt = 1 # 연속된 칸의 개수
        for j in range(N-1):

            v = arr[i][j+1] - arr[i][j] if d else arr[j+1][i] - arr[j][i]
            if v == 0:
                cnt += 1
            elif v == 1 and cnt >= L: # 오르막은 낮은 칸이 L개 이상인지 바로 확인 가능
                cnt = 1 # L개 이상이면 연속된 칸의 개수를 1로 초기화
            elif v == -1 and cnt >= 0: # 내리막은 낮은 칸의 개수를 바로 확인 불가능
                cnt = 1-L # 내리막 초반에 연속된 칸의 개수를 음수로 변경
            else:
                return
        if cnt >= 0:
            ret += 1

    for i in range(N):
        slope(i, 1)
        slope(i, 0)
    return ret

print(solution())

• 결과는 72 ms 나왔다.

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋