[BOJ/python] 14890번 경사로

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

14890번: 경사로

문제 해석

 

주어진 배열에 가로세로 즉 2n개를 검사하여 해당 길이 지나갈 수 있는지 파악하는 문제이다.

지나갈 수 있는 조건은 해당 길의 높이가 같아야하고, 높이의 차이가 1이라면 길이가 l인 경사로를 설치하여 지나갈 수 있다.

경사로의 갯수의 제한은 없으며 경사로가 중복으로 설치될 수 없다.

 

문제는 이해하는데 어렵지 않다!

---

코드

 

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

def check(road):
    use = [0] * n
    flag = True

    for i in range(0, n - 1):
        if road[i] == road[i + 1]: continue
        elif road[i] + 1 == road[i + 1]: # 1 1 1 2 2 2
            for k in range(l):
                if 0 <= i - k < n and use[i - k] == 0:
                    if road[i] == road[i - k]: continue
                flag = False
            if flag:
                for k in range(l):
                    use[i - k] = 1
        
        elif road[i] - 1 == road[i + 1]: # 3 2 2 1 1 1
            for k in range(l):
                if 0 <= i + 1 + k < n:
                    if road[i + 1] == road[i + 1 + k] and use[i + 1 + k] == 0: continue
                flag = False
            if flag:
                for k in range(l):
                    use[i + 1 + k] = 1
        
        else: flag = False
    
    return flag

ans = 0
for i in range(n):
    if check(arr[i]): ans += 1
arr = list(zip(*arr))
for i in range(n):
    if check(arr[i]): ans += 1
print(ans)

---

문제 풀이

 

2차원 배열 그대로두고 이중 포문을 통해 문제를 해결하려 했지만 너무 복잡했다. 따라서 길 1개만 인자로 입력받고, 해당 길을 지날수 있는지 체크하는 check함수를 구현하여 문제를 해결했다. 

check 함수에서는  중복으로 경사로를 설치하면 안되기 때문에 설치한 경사로를 나타내는 use 배열을 선언해 주었다.

길의 i번째와 i+1이 같다면 상관 없으므로 통과

길의 i번째가 i+1번째 길보다 높이가 1칸 낮다면 즉 1 1 1 2 2 2 와 같은 상황이라면 i 부터 i - l까지 경사로를 설치할 수 있는지 확인해주어야 한다. 따라서 반복문을 통해 확인해 주었다.

이후 설치할 수 있게된다면 경사로를 사용했으므로 다시한번 반복문을 통해 use배열에 맞는 위치에 1값으로 세팅해주었다.

길의 i 번째가 i+1  번째 길보다 높이가 1칸 높다면 즉  2 2 2 1 1 1와 같은 상황이라면 i + 1 부터 i + 1 + l까지 경사로를 설치할 수 있는지 확인해야 한다. 이 또한 위 방법과 같이 확인해주었다.

 

list(zip(*arr)) 함수는 해당 배열을 돌려주는 함수이다.