[BOJ][🟡3][백준#14890] 경사로

문제 출처

BAEKJOON Online Judge #14890

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.  오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.  다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

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

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

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

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

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다. 가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

예제

예제 1

입력

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

출력

3

예제 2

입력

6 2
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

출력

7

예제 3

입력

6 3
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

출력

3

예제 4

입력

6 1
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

출력

11

My Sol

def main(arr):
    global N, L
    check = [0]*N
    std = arr[0]

    def check_float(part):
        global N, L
        std = part[0]
        for p in part:
            if p != std: return 0
        return 1

    i = 1
    while i < N:
        # 높이차가 1 초과
        if abs(arr[i]-std) > 1: return 0
        # 높이가 같음
        elif arr[i]==std: i+=1
        # 높이가 1 작아짐
        elif arr[i]+1 == std:
            if i+L > N: return 0
            if not check_float(arr[i:i+L]): return 0
            for k in range(i, i+L):
                check[k] = 1
            i += L
            std -= 1

        # 높이가 1 높아짐
        elif arr[i]-1 == std:
            if i-L < 0: return 0
            # 1. 뒤의 경사로 구간이 모두 평평한지 체크
            if not check_float(arr[i-L:i]): return 0
            # 2. 뒤에 경사로가 없었는지 체크
            for k in range(i-L, i):
                if check[k]: return 0
            for k in range(i-L, i):
                check[k] = 1
            i += 1
            std += 1

    return 1


N, L = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
    road = mat[i]
    ans += main(road)

for j in range(N):
    road = []
    for i in range(N):
        road.append(mat[i][j])
    ans += main(road)

print(ans)

구현 문제였다.

1. NxN의 2차원 배열에서 한 행과 열을 기준으로 조회하기 때문에 1차원 배열에 독립적이다. 때문에 각 행과 열을 arr로 함수에 인자로 전달하여 판별하는 main 함수를 두었다.
2. main함수는 가능하다면 1, 안 된다면 0을 반환하고, 전역 반복에서는 ans에 이를 반환값을 더해 출력한다.
3. main 함수의 내부는 경사로의 존재 유무를 확인하는 check 1차원 배열을 따로 둔다.
4. 시작점인 arr[0]을 std로 두고, 이후 arr의 한 칸씩 인덱스를 높이며 진행한다.
5. 경우 1. 경사로가 높아지거나 낮아지는데 변화가 1 초과인 경우를 먼저 따진다. 이 경우 따질 것도 없이 불가능하므로 0을 return 한다.
6. 경우 2. 만약 높이가 같다면 따질 것도 없이 다음 인덱스로 넘어간다.
7. 경우 3. 높이가 낮아진다면 앞으로 경사로를 두어야 하므로 앞의 경사로를 두는 구간이 평평한지 체크한다. 이를 check_float 함수를 따로 두어 구간을 인자로 전달하고 독립적으로 체크한다. 이제 생각해보니 set으로 두고 길이가 1 이상인지 아닌지만 체크하면 될 것 같다.
8. 평평하지 않다면 불가능이므로 0을 반환하고, 평평하다면(part가 모두 같은 값) 해당 경사로 구간의 인덱스만큼 check에 1을 체크한다. 향후 높이가 한 칸 높아져서 경사로를 이전으로 두어야 할 때, check 배열을 확인하여 경사로가 이미 두어져있는 공간이 아닌지 체크한다.
9. 경사로를 L만큼 두었으므로 인덱스를 L만큼 추가하고 std를 1 낮춰준다.
10. 경우 4. 높이가 한 칸 높아진다면 이미 온 방향으로 경사로를 두어야 하므로 1) 뒤의 경사로를 두는 구간이 평평한지 체크하고, 2) 경사로가 이미 있지는 않는지 체크하는 2중 체크가 필요하다.
11. 이 중 하나라도 만족하지 못한다면 0을 반환, 아니라면 구간만큼 check에 체크를 해주고, std를 1 높여준 뒤, 다음 인덱스로 넘어간다.

결과

맞았습니다!!

모범답안

출처

# empty