[백준] 경사로 - python (14890번)

풀이 전략

행과 열, 총 2N개의 리스트를 차례로 탐색하며 경사로를 설치할 수 있는지 확인하면 된다고 생각하였습니다. 함수로 구현하지 않아도 되지만 함수로 구현하면 중간중간 경사로 설치가 불가능 할 때 return문으로 빠져나올 수 있는 장점이 있습니다.

풀이 과정

1. 행, 열을 하나씩 함수에 넣어 경사로를 만들 수 있는지 체크

2. 경사로 체크

함수가 행을 입력변수로 받습니다.
이후 인접한 2개의 수를 하나 씩 체크하게 됩니다. 예를들어 입력 받은 행이 [1,2,3,4]이라면 1,2 / 2,3 / 3,4 이렇게 짝으로 확인합니다.

1) 앞에 숫자가 1 클 때

• 뒤에 경사로를 설치할 수 있는 칸이 L개 있는지 (index out of range 제외 용)
• 뒤에 L개의 칸이 높이가 다 동일한지
• 높이가 같다면 경사로를 설치했다고 체크

2) 뒤에 숫자가 1 클 때

• 앞에 경사로를 설치할 수 칸이 L개 있는지 (index out of range 제외 용)
• 앞에 L개의 칸이 높이가 다 동일한지
• 이미 경사로를 설치한 칸이 있는지
• 위의 조건을 다 만족한다면 경사로를 설치했다고 체크

3. 전치 행렬 만들어서 반복하기

처음 board의 행들을 check함수에 넣어서 다 확인 후 board를 전치시키면 열이 행이 되기 때문에 전치 시킨 후 반복합니다

import sys

# input = sys.stdin.readline
sys.stdin = open('input.txt')

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

'''
1. 한 줄에서 왼쪽부터 탐색
2. 높이가 이전꺼랑 다르면 경사로를 설치할 수 있는지 확인
3. 높이가 이전 것 보다 높으면
    1) 높이 차이가 1인지 확인
    2) 이전 L개의 칸의 높이가 같은지 확인
    3) 이전 L개의 칸에 경사로가 설치된 적이 있는지 확인
4. 높이가 이전 것 보다 낮으면
    1) 높이 차이가 1인지 확인
    2) 본인 포함 L개의 칸의 높이가 같은지 확인
'''

def check(a):
    installed = []  # 경사로가 설치된 칸의 인덱스 저장
    i, j = 0, 1
    while j < N:
        print(i, j)
        # 앞에가 한 칸 높을 때
        if a[i] == a[j] + 1:
            print('앞에가 높음')
            # 뒤에 L개가 있는지 부터 확인 (index out of range)
            if j + L > N:
                return 0
            else:
                print(f'뒤에 ${L}개 있음')
                # j부터 L개의 높이가 같은지 확인
                tmp = len(set(a[j: j + L]))
                if tmp != 1:
                    return 0
                else:
                    print('높이 같음')
                    for k in range(j, j + L):
                        installed.append(k)
        # 뒤에가 한 칸 높을 때
        elif a[i] == a[j] - 1:
            print('뒤에가 높음')
            # 앞에 L개가 있는지 부터 확인 (index out of range)
            if i - L + 1 < 0:
                return 0
            else:
                print(f'앞에 {L}개 있음')
                # i부터 왼쪽으로 L개의 높이가 같은지 확인
                tmp = len(set(a[i - L + 1: i + 1]))
                if tmp != 1:
                    return 0
                else:
                    print('높이 같음')
                    # 설치가 되있으면 return 0, 아니면 설치
                    for k in range(i - L + 1, i + 1):
                        if k in installed:
                            return 0
                        else:
                            print('새로 설치')
                            installed.append(k)
        elif a[i] > a[j] + 1 or a[j] > a[i] + 1:
            return 0

        i += 1
        j += 1
    return 1

ans = 0
for i in range(N):
    ans += check(board[i])

board = list(zip(*board))
for i in range(N):
    ans += check(board[i])
print(ans)

구현 문제는 항상 어렵다고 생각합니다.. 어떤 자료구조를 사용하느냐, 어떤 방법을 사용하느냐에 따라 완전히 달라진 로직과 실행 시간을 가지기 때문입니다.