백준 #14890 - [G3] 경사로 : 구현

(python)

 

아이디어

일단 연속된 숫자가 L 번 이상 나와야 경사로를 놓을 수 있고, 1칸 차이여야 경사로를 배치해서 지나갈 수 있습니다.

핵심이 되는 아이디어는 "길의 표현법을 수정해서 연속된 번호의 횟수로 표현하겠다" 입니다. (층,연속횟수) 의 배열로 나타냈습니다. (지금은 튜플로 표현했지만 뒤에서 연속횟수를 변경해주어야해서 코드 상에서는 list 를 사용했습니다.)

예를 들어서 [3 2 1 1 2 3] 를 [(3,1), (2,1), (1,2), (2,1), (3,1)]  로 표현을 바꿔주는겁니다.

이렇게 바꾸면서 1. 층이 바뀌는 부분을 바로 알 수 있다. 2.경사로를 놓을 수 있는지 바로 체크할 수 있다. 두가지 장점이 생깁니다.

여기에서 층이 바뀔때마다 1층씩 변경됐는지, 1층 변경됐으면 경사로를 놓을 수 있는지 (= 더 낮은 층의 연속 횟수가 L 이상인지) 확인하고 경사로를 놓을 수 있다면 더 낮은 층의 연속 횟수에서 L을 빼주고 넘어갑니다. (경사로를 놓고 지나간걸 표현)

이렇게 해서 걸리는 부분 없이 길을 끝까지 갔다면 지나갈 수 있는 길이란걸 알 수 있습니다.

 

코드

def solution(input) : 
	# 맵 정보 받아오기
    N,L = list(map(int, input().split()))
    MAP = []
    for _ in range(N) :
        MAP.append(list(map(int,input().split())))
    
    # 갈 수 있는 길인지 체크
    def can_go(map) :
    	# 길 표현법 수정
        cmap = [[map[0],0]]
        for i in map :
            if i == cmap[-1][0] :
                cmap[-1][1] += 1
            else :
                cmap.append([i,1])
                
        # 길 가보기
        for i in range(len(cmap)) :
            if i == 0 : continue
            if cmap[i-1][0] == cmap[i][0] + 1 : # 내려가는 경사로
                if cmap[i][1] >= L : cmap[i][1] -= L
                else : return False
            elif cmap[i-1][0] == cmap[i][0] -1 : # 올라가는 경사로
                if cmap[i-1][1] >= L : cmap[i-1][1] -= L
                else : return False
            else : return False
        return True # 걸리는 부분 없이 통과헀으면 성공
    
    MAP_col = [] # 세로길 만들기
    for c in range(N) :
        m = []
        for r in range(N) :
            m.append(MAP[r][c])
        MAP_col.append(m)
	
    # 가로길, 세로길 모두 탐색하기
    cnt = 0
    for m in MAP :
        cnt += can_go(m)
    for m in MAP_col :
        cnt += can_go(m)
    print(cnt)

solution(input)