116. [삼성기출12]Python 백준 14890 번 경사로 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14890 번 경사로 입니다.

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

14890번: 경사로

 

먼저 백준 14890 번 경사로 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

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

def isWay(way):
    isInstalled = [False for _ in range(N)]
    for i in range(N - 1):
        if abs(way[i] - way[i + 1]) > 1:
            return False

        if way[i] > way[i + 1]:
            if i + 1 + L > N: #경사로 길이 체크
                return False
            for l in range(L):
                if isInstalled[i + 1 + l]: #이미 설치 되어 있는지 체크
                    return False
                if way[i+1] != way[i + 1 + l]: #바닥이 평평한지 체크
                    return False

            #경사로 설치
            for l in range(L):
                isInstalled[i + 1 + l] = True

        if way[i] < way[i + 1]:
            if i + 1 - L < 0:
                return False
            for l in range(L):
                if isInstalled[i - l]:
                    return False
                if way[i] != way[i - l]:
                    return False

            for l in range(L):
                isInstalled[i - l] = True

    return True

cnt = 0

for i in range(N):
    if isWay(board[i]): #가로
        cnt += 1
    if isWay([board[j][i] for j in range(N)]): #세로
        cnt += 1

print(cnt)

 

문제 접근

모든 열과 행을 한번씩 확인하면서 길인지 아닌지 파악합니다.

길이 아닌 조건

1. 높이 차이가 2 이상 나는 경우

2. 경사로를 설치할만한 길이가 나오지 않는 경우

3. 이미 다른 경사로가 설치되어 있는 경우

4. 경사로가 설치될 바닥이 평평하지 않은경우 

 

Python 코드 구현

 

리스트를 입력받고 길이면 True, 아니면 False를 출력하는 함수를 구현합니다.

이때 경사로의 설치 여부를 저장하는 리스트 isInstalled도 같이 구현합니다.

def isWay(way):
    isInstalled = [False for _ in range(N)]

 

먼저 리스트를 돌면서 높이 차이가 2칸 이상 난다면 길이 아니라고 판단합니다.

for i in range(N - 1):
    if abs(way[i] - way[i + 1]) > 1:
        return False

 

왼쪽이 오른쪽보다 높고 높이차이가 1인 구역이 있는 경우입니다.

if way[i] > way[i + 1]:

 

경사로를 설치할 만한 길이가 되는지 파악하고

if i + 1 + L > N: #경사로 길이 체크
    return False

 

이미 설치 되어있는지, 바닥이 평평한지 확인합니다.

for l in range(L):
    if isInstalled[i + 1 + l]: #이미 설치 되어 있는지 체크
        return False
    if way[i+1] != way[i + 1 + l]: #바닥이 평평한지 체크
        return False

 

경사로를 설치할 조건이 갖춰지면 설치하면 됩니다.

#경사로 설치
for l in range(L):
    isInstalled[i + 1 + l] = True

 

오른쪽이 왼쪽 보다 높고 높이차이가 1인 구역이 있는 경우입니다.

마찬가지로 경사로 설치 조건들을 살펴본 후 설치합니다.

if way[i] < way[i + 1]:
    if i + 1 - L < 0:
        return False
    for l in range(L):
        if isInstalled[i - l]:
            return False
        if way[i] != way[i - l]:
            return False

    for l in range(L):
        isInstalled[i - l] = True

 

이렇게 모든 구역을 살핀 후에 경사로를 설치 가능하거나, 높이가 같은 경우 길이라고 판단합니다.

return True

 

각 구역을 가로, 세로로 나누어 검사하고, 길이라면 cnt 를 1 증가시킵니다.

cnt = 0

for i in range(N):
    if isWay(board[i]): #가로
        cnt += 1
    if isWay([board[j][i] for j in range(N)]): #세로
        cnt += 1

 

검사가 끝났다면 출력합니다.

print(cnt)

 

파이썬 백준 14890 번 경사로 최종 코드입니다. 

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

def isWay(way):
    isInstalled = [False for _ in range(N)]
    for i in range(N - 1):
        if abs(way[i] - way[i + 1]) > 1:
            return False

        if way[i] > way[i + 1]:
            if i + 1 + L > N: #경사로 길이 체크
                return False
            for l in range(L):
                if isInstalled[i + 1 + l]: #이미 설치 되어 있는지 체크
                    return False
                if way[i+1] != way[i + 1 + l]: #바닥이 평평한지 체크
                    return False

            #경사로 설치
            for l in range(L):
                isInstalled[i + 1 + l] = True

        if way[i] < way[i + 1]:
            if i + 1 - L < 0:
                return False
            for l in range(L):
                if isInstalled[i - l]:
                    return False
                if way[i] != way[i - l]:
                    return False

            for l in range(L):
                isInstalled[i - l] = True

    return True

cnt = 0

for i in range(N):
    if isWay(board[i]): #가로
        cnt += 1
    if isWay([board[j][i] for j in range(N)]): #세로
        cnt += 1

print(cnt)

 

백준 14890 번  경사로 자세한 설명 및 Python 코드였습니다.

감사합니다.