[Python] 백준 14890번: 경사로

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

14890번: 경사로

 

import sys
input = sys.stdin.readline


def getPossiblePathCount():
    possiblePathCount = 0

    # 가로
    for i in range(N):
        isValidPath = True
        isRunwayPut = [False]*N

        for j in range(N-1):
            c, n = heights[i][j], heights[i][j+1]

            # 같을 경우
            if c == n:
                continue

            # 1 2
            elif c+1 == n:
                flag = True

                # 경사로 놓기
                for k in range(j-L+1, j+1):
                    if k < 0 or heights[i][k] != c or isRunwayPut[k] == True:
                        flag = False
                        break
                    else:
                        isRunwayPut[k] = True

                # 경사로 놓기에 실패
                if not flag:
                    isValidPath = False
                    break
            # 2 1
            elif c == n+1:
                flag = True

                # 경사로 놓기
                for k in range(j+1, j+L+1):
                    if k > N-1 or heights[i][k] != n or isRunwayPut[k] == True:
                        flag = False
                        break
                    else:
                        isRunwayPut[k] = True

                # 경사로 놓기에 실패
                if not flag:
                    isValidPath = False
                    break

            # 높이 차이가 2 이상
            else:
                isValidPath = False
                break

        if isValidPath:
            possiblePathCount += 1

    # 세로
    for j in range(N):
        isValidPath = True
        isRunwayPut = [False]*N

        for i in range(N-1):
            c, n = heights[i][j], heights[i+1][j]

            # 같을 경우
            if c == n:
                continue

            # 1 2
            elif c+1 == n:
                flag = True

                # 경사로 놓기
                for k in range(i-L+1, i+1):
                    if k < 0 or heights[k][j] != c or isRunwayPut[k] == True:
                        flag = False
                        break
                    else:
                        isRunwayPut[k] = True

                # 경사로 놓기에 실패
                if not flag:
                    isValidPath = False
                    break
            # 2 1
            elif c == n+1:
                flag = True

                # 경사로 놓기
                for k in range(i+1, i+L+1):
                    if k > N-1 or heights[k][j] != n or isRunwayPut[k] == True:
                        flag = False
                        break
                    else:
                        isRunwayPut[k] = True

                # 경사로 놓기에 실패
                if not flag:
                    isValidPath = False
                    break

            # 높이 차이가 2 이상
            else:
                isValidPath = False
                break
        if isValidPath:
            possiblePathCount += 1

    return possiblePathCount


if __name__ == '__main__':
    N, L = map(int, input().split())
    heights = [list(map(int, input().split())) for _ in range(N)]

    possiblePathCount = getPossiblePathCount()
    print(possiblePathCount)

 

딱히 특수한 알고리즘이 필요하진 않고, 하라는대로 하면 풀리는 문제이다.

 

크게 이중 for문을 돌게 되는데, 내부 for문을 다 돈 이후에, isValidPath가 True인 채로 '무사히 통과'하게 되면 이 길은 지나갈 수 있는 길이 되는 것이다.

 

내부 for문을 설명하자면, 비교 대상 2개(c: current, 현재, n: next, 다음)에 대해

1. 높이가 같을 경우, 2. c+1 == n 3. c == n+1 4. 높이 차이가 2 이상일 경우

라는 4가지 경우로 나누어 푼다.

여기서 중요한 건 2, 3번째 경우이다. L이 2라고 했을 때, '112'에서 c=1, n=2일 때를 살펴보자. 이 경우 연속된 2개의 1(즉, 경사로를 놓고자 하는 범위)에 대해 k에 대한 for문을 돌아주면서, 1. 인덱스를 초과하지 않았으면서 2. c와 값이 같으며 3. 경사로가 아직 없는 경우 라는 3개의 조건을 충족시키면 경사로를 놓는다.

 

이외에는 딱히 설명이 필요한 부분이 없으니, 구체적으로 설명하진 않는다.(주석 참고)