[백준 14890번] 경사로 - Python

문제 링크

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

14890번: 경사로

 

풀이 

조건에 따라 구현하면 되는 문제인데, 뭔가 되게 복잡(?)하게 생각해서 예외처리를 계속 하다가 결국 못풀어서 다른 블로그를 참고했다. 

각 라인에 대해 지나갈 수 있는 길인지 체크한다. 

세로의 경우 파이썬의 zip을 사용하여 간단하게 n*m->m*n 배열로 변경할 수 있고, 이에 대해 체크하면 된다. 

 

시작점을 오른쪽/ 왼쪽으로 구분하여 지나가며 갈 수 있는 길인지 체크한다. 

만약 다음 칸과의 차이가 1보다 크면 False를 리턴한다. 

 

1. 오른쪽으로 지나갈 때 

다음 칸의 높이가 현재 칸의 높이 + 1일 때, 현재 칸부터 l만큼 전 칸까지 확인하여 경사로를 놓을 수 있는지 체크한다. 

범위를 벗어나거나, 이미 경사로가 설치되어 있거나, 높이가 다르면 False를 리턴한다. 

경사로를 놓을 수 있는 위치이면 used 배열 (경사로 설치 유무 체크)의 인덱스 값을 True 로 설정한다. 

 

2. 왼쪽으로 지나갈 때 

현재 칸의 높이가 다음 칸의 높이 + 1일 때, 다음 칸 부터 l만큼 다음 칸까지 확인하여 경사로를 놓을 수 있는지 체크한다.

범위를 벗어나거나, 이미 경사로가 설치되어 있거나, 높이가 다르면 False를 리턴한다. 

경사로를 놓을 수 있는 위치이면 used 배열 (경사로 설치 유무 체크)의 인덱스 값을 True 로 설정한다. 

 

def check(arr):
    used = [False] * n

    for i in range(n-1):
    	# 높이 차이가 1 이상 
        if abs(arr[i] - arr[i+1]) > 1 :
            return False
		
        # 오른쪽 탐색 
        if arr[i] < arr[i+1]:
            for j in range(l):
                if i-j < 0 or used[i-j] or arr[i] != arr[i-j]:
                    return False

                used[i-j] = True
                
         # 왼쪽 탐색 
        if arr[i] > arr[i+1]:
            for j in range(l):
                if i + j + 1 >= n or used[i+j+1] or arr[i+1] != arr[i+j+1]:
                    return False

                used[i+j+1] = True

    return True

n, l = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

ans = 0

for i in graph:
    if check(i):
        ans += 1

for i in list(zip(*graph)):
    if check(i):
        ans += 1

print(ans)