[백준] 14890번 - 경사로

14890번: 경사로

해당 문제는 완전탐색 문제로 문제에 주어진 조건에 맞게 모두 탐색을 해보아 경우의 수를 구하면 된다.

1. 길을 지나갈 수 있으려면 모든 칸의 높이가 같아야한다.
2. 높이가 다른경우 경사로를 놓아서 길을 만들 수 있다.
3. 경사로의 높이는 항상 1이며, 길이는 L이다.
4. 경사로를 놓을 낮은칸의 높이는 모두 같아야하고, L개의 연속되어 있어야한다.

따라서 다음과 같은 조건으로 문제를 해결할 수 있다.

이전위치와 현재위치의 높이 차이는 반드시 1이어야한다.

1. 현재위치 높이 > 이전위치 높이 : 이전에 있던 위치들이 길이가 L이어야한다. 또한 중복 경사로 만들기 불가
2. 현재위치 높이 < 이전위치 높이 : 현재위치 다음에 있는 위치들의 길이가 L이어야한다.

중복 경사로를 만들기는 불가한 경우는 이전에 경사로를 만들었을 경우이다.

xdfs와 ydfs로 문제를 해결하였으며 해당 함수는 각각 x축의 경사로 확인, y축의 경사로 확인 문제이다.

N, L = map(int, input().split())

table = []
for _ in range(N):
    table.append(list(map(int, input().split())))

moves = [(0, 1), (1, 0)]

# count는 현재 같은 숫자가 얼마나 나왔는지 카운트한다.
def xdfs(i,j):
    prev = table[i][j]
    j += 1
    while N > j:
        cur = table[i][j]
        if prev != cur: # 값이 다르다면
            if abs(prev - cur) > 1:
                return 0

            counter = 0
            if cur > prev: # 현재 값이 이전값보다 크다면 이전에 있던 높이를 확인해본다.
                for t in range(j-1, -1, -1):
                    temp = table[i][t]
                    if prev == temp and not visited[t]:
                        visited[t] = True
                        counter += 1
                        if counter >= L:
                            break
                    else:
                        break
            else: # 현재값이 이전값보다 작다면 이후에 나올 높이를 확인해본다.
                for t in range(j, N):
                    temp = table[i][t]
                    if cur == temp and not visited[t]:
                        visited[t] = True
                        counter += 1
                        j = t
                        if counter >= L:
                            break
                    else:
                        break

            if counter < L:
                return 0

        j += 1
        prev = cur

    return 1

def ydfs(i,j):
    prev = table[i][j]
    i += 1
    while N > i:
        cur = table[i][j]
        if prev != cur: # 값이 다르다면
            if abs(prev - cur) > 1:
                return 0

            counter = 0
            if cur > prev: # 현재 값이 이전값보다 크다면 이전에 있던 높이를 확인해본다.
                for t in range(i-1, -1, -1):
                    temp = table[t][j]
                    if prev == temp and not visited[t]:
                        visited[t] = True
                        counter += 1
                        if counter >= L:
                            break
                    else:
                        break
            else: # 현재값이 이전값보다 작다면 이후에 나올 높이를 확인해본다.
                for t in range(i, N):
                    temp = table[t][j]
                    if cur == temp and not visited[t]:
                        visited[t] = True
                        counter += 1
                        i = t
                        if counter >= L:
                            break
                    else:
                        break

            if counter < L:
                return 0

        i += 1
        prev = cur

    return 1

answer = 0
for i in range(N):
    visited = [False for _ in range(N)]
    ans = xdfs(i, 0)  # y축
    #print("x축", i, 0, ans, visited)

    answer += ans

for i in range(N):
    visited = [False for _ in range(N)]
    ans = ydfs(0, i)  # y축
    #print("y축", 0, i, ans, visited)
    answer += ans

print(answer)