[삼성SW역량][Python/BOJ] 백준 14890 경사로(구현)

 

 

 

 

 

 

 

 

 

 

 

main에서는

가로와 세로를 차례대로 검사하고 check 함수의 결과가 True인 경우 ans의 값을 늘려준다.

 

 

check함수는 

 

 

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

 

 

이러한 경우 return False 를 하고 만약 함수의 끝까지 도달할 경우 retrun True를 한다. 

True한 경우가 길이 있는 경우이다. 

 

 

 

 

 

---

 

 

 

 

 

코드 : 

def check(now) : # 한 행 또는 열을 지나갈 수  있는지 검사 
    for i in range(1,n) : 
        if abs(now[i-1] - now[i]) > 1 :  return False # 차이가 1이상이라면 
        
        if now[i-1] > now[i] : # 왼쪽이 더 크다면 오른쪽 확인 
            for k in range(l) : # l만큼의 공간이 있는지 확인 
                if i+k >=n or now[i+k] != now[i] or vis[i+k] :  # 구역을 벗어나거나 높이가 동일하지않거나 경사로를 쌓은적이 있다면 
                    return False 
                vis[i+k] =1 # 여기 경사로 쌓았어 
        elif now[i-1] < now[i] : # 오른쪽이 더 크다면 왼쪽 확인 
            for k in range(l) :
                if i-1-k <0 or now[i-1-k]!=now[i-1] or vis[i-1-k] :# 구역을 벗어나거나 높이가 동일하지않거나 경사로를 쌓은적이 있다면
                    return False 
                vis[i-1-k] = 1 # 여기 경사로 쌓았어 
    return True  # 여기 길 있어 

            
if __name__=="__main__" :
    n,l = map(int,input().split())
    mp = [list(map(int,input().split())) for i in range(n)]
    ans = 0
    
    #  가로
    for i in range(n) :
        vis = [0] * n 
        if check(mp[i]) : ans+=1 
    
    # 세로
    for i in range(n) :
        vis = [0] * n 
        if check([mp[j][i] for j in range(n)]) :
            ans+=1 
    print(ans)

 

 

 

 

 

다른 코드 : 

def check(ch) :
    vis = [0]*n
    for i in range(1,n ) :
        # 높이는 항상 1만 가능하므로 
        if abs(ch[i] - ch[i-1])>1 : return False 
        
        # 오른쪽이 더 크면 
        if ch[i] > ch[i-1] : 
            # 왼쪽 탐색 
            # i-1 부터 왼쪽으로 l 만큼 높이가 같은지 확인 
            for j in range(l) :
                if (i-1-j) <0 or vis[i-1-j] != 0 or ch[i] - ch[i-1-j] != 1 :
                    return False 
                vis[i-1-j] = 1 
        # 왼쪽이 더 크면         
        elif ch[i] < ch[i-1] : 
            # 오른쪽 탐색 
            # i 부터 오른쪽으로 l 만큼 높이가 같은지 확인 
            for j in range(l) :
                if i+j >= n or vis[i+j]!=0 or ch[i-1] - ch[i+j] != 1 :
                    return False 
                vis[i+j] = 1 
    return True 
                    
    
if __name__=="__main__" :
    n,l = map(int,input().split())
    mp = [list(map(int,input().split())) for _ in range(n)]
    ans = 0
    
    # 가로 
    for i in mp :
        if check(i) :
            ans +=1 
    
    # mp 뒤집기 
    mp = list(zip(*mp))

    # 세로 
    for i in mp :
        if check(i) :
            ans +=1 
    
    print(ans)

 

 

 

 

 

 

참고 블로그 : 

 

https://ryu-e.tistory.com/108

[Python] 백준 14890 경사로

 

 

복습 : 

✅ 20220716

✅ 20220826