[Python][구현] 백준 14890번 (경사로)

요구능력

구현

 

문제풀이

이 문제는 길에다 경사로를 만들고 길을 통과할 수 있는지를 묻는 문제이다.

구현을 깔끔하게 짜려면 큰 조건 -> 작은 조건을 잘 구상해야하는것 같다.

 

내 생각의 흐름대로 정리해보면

내가 하나의 길에서 출발한다고 생각해보자.

그럼 다음번 칸 갈 수 있느냐 없느냐가 이 문제의 관건이다.

조건을 다 읽어보면 다음번 칸을 갈 때 칸의 높이가 같으면 그냥 지나갈 수 있다.

하지만, 칸의 높이가 다르다면 그냥 지나갈 수 없다.

이 때, 생각할 수 있는게 칸의 높이가 계속 같으면 그 길은 통과가 된다는 것이다.

그렇다면 따로 처리해줄 것은 없는것이다.

 

하지만 만약, 현재 칸의 높이와 다음번 칸의 높이가 다를경우에는 칸의 차이가 1이어야하고 그 이외의 경우에는 다음 칸을 진행할 수 없다.

if road[i] != road[i + 1]:
    if abs(road[i] - road[i+1]) > 1 :
        return False

만약 칸의차이가 1이면 다음번 칸이 더 낮은 칸일 것이다.

높은 칸(i) -> 낮은 칸(i + 1)으로 갈 경우 경사로를 깔기위해서 고려해야하는 것들을 생각해보자.

현재 낮은칸 ~ 현재낮은칸 + L개 만큼이 현재낮은 칸의 높이와 같은지 확인해야할 것이다.

그러기 위해서 경사로가 깔렸을 때 길이 끝나버리면 경사로도 깔지못하는 경우를 처리해준다.

그리고 현재칸의 높이를 check에 저장해두고, 현재 낮은칸 -> 현재낮은칸 +L 개까지 탐색을 해준다.

이때, 이미 경사로를 놓은곳이 있다면 탐색을 멈추고 이 길은 더이상 진행이 불가한 길이므로 False를 리턴해준다.

그리고 경사로를 겹쳐서 놓는경우는 안된다고 했으므로 visited[]리스트를 활용해서 경사로를 세운 칸에는 1로 표시를 해준다.

 

칸의 차이가 -1이면 다음번 칸이 더 높은 칸일 것이다.

경사를 만드려면 낮은칸 - L 만큼의 칸이 필요하다. 그만큼의 칸이 없다면 False를 리턴해준다.

그리고 현재 낮은칸부터 현재 낮은칸 - L 칸을 모두 탐색하면서 칸의 높이가 현재낮은칸과 같은지, 이미 경사가 있지는 않은지를 확인해준다.

if road[i] - road[i + 1] == 1:
        if i+1+l > n:
            return False
        check = road[i + 1]
        for j in range(i+1, i+1+l):
            if visited[j] or road[j] != check:
                return False
            visited[j] = 1
    elif road[i] - road[i + 1] == -1:
        if i - l < - 1:
            return False
        check = road[i]
        for j in range(i, i-l, -1):
            if visited[j] or road[j] != check:
                return False
            visited[j] = 1

후기

풀다가 코드가 지저분해지고 점점 복잡해져서 다른분것을 참고하고 풀었다..

길을 하나씩 검사하는건 맞췄는데, 경사로가 겹치는 부분을 구현하지 못했다.

구현 깔끔하게 푸시는분들보면 신기하다.

코드

n, l = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

def check_route(road):
    global n, l
    visited = [0] * n
    for i in range(n - 1):
        if road[i] != road[i + 1]:
            if abs(road[i] - road[i+1]) > 1 :
                return False
            else:
                if road[i] - road[i + 1] == 1:
                    if i+1+l > n:
                        return False
                    check = road[i + 1]
                    for j in range(i+1, i+1+l):
                        if visited[j] or road[j] != check:
                            return False
                        visited[j] = 1
                elif road[i] - road[i + 1] == -1:
                    if i - l < - 1:
                        return False
                    check = road[i]
                    for j in range(i, i-l, -1):
                        if visited[j] or road[j] != check:
                            return False
                        visited[j] = 1
    return True

result = 0
for row in arr:
    if check_route(row):
        result += 1

for columns in range(n):
    if check_route( [arr[row][columns] for row in range(n)]):
        result += 1

print(result)