[백준 14890번] 파이썬 - 경사로

백준 14890_경사로

시간 제한 2초, 메모리 제한 512MB

# 조건

• 크기가 N x 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보다 작거나 같은 자연수이다.

출력

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

---

# 접근 방법

• 주어진 경사로를 놔두는 조건을 잘 충족시키면서 브루트 포스로 구현하면 되는 문제이다.
• 0행부터 N-1행까지 검사한다고 가정하였을 때, 칸을 이동하며 2칸 이상 차이가 나는 경우에는 break를 걸어주고, 1칸 차이라면 낮은 칸의 개수를 Flag로 처리하여 L개 이상 연속하는지 체크해주면 된다.
  • 높은 칸에서 낮은 칸으로 내려가는 경우는 idx를 이어서 탐색해주면 되지만
  • 낮은 칸에서 높은 칸으로 올라가는 경우에는 역으로 탐색해주어야 한다.
  • 즉, 2 2 1 1 1 와 같은 경우 1로 넘어가는 경우에는 1을 flag로 cnt가 몇 개인지 그대로 가면 되지만
  • 1 1 1 2 2 와 같은 경우 2로 넘어가는 곳에서 idx-1 씩 해주며 flag를 1로 체크 cnt를 세주어야 한다.
  • 다음 칸과의 비교가 필요하므로 2중 for문의 안쪽 for문은 0 ~ N-2까지만 해준다.
• 여기서 겹치게 경사로를 놔두는 경우를 체크해주지 않아 Fail을 받았다.
  • 각 행 또는 마다, 돌아가서 체크하는 경우 visited를 체크해주는 로직을 추가해주어야 한다.
  • 바깥 반복문이 바뀌는 경우에 visited를 [0] * N개 만들어 준 후 경사로를 놔두는 경우 1로 변경해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def check(res):  
    for i in range(N):  
        visited = [0] * N  
        for j in range(0, N-1):  
            if arr[i][j] == arr[i][j+1]:  
                continue  
            # 2 2 1 1 과 같이 높은 곳에서 낮은 곳으로 내려가는 경우  
            elif arr[i][j] - arr[i][j+1] == 1:  
                # arr[i][j+1]을 flag로 연속되는 개수가 L이상인지 체크해주기  
                flag = arr[i][j+1]  
                cnt = 0  
                idx = j+1  
                can_go = True  
                while cnt < L:  
                    # 범위 내이고 동일하다면 +1  
                    if idx < N:  
                        if arr[i][idx] == flag and visited[idx] == 0:  
                            visited[idx] = 1  
                            cnt += 1  
                            idx += 1  
                            continue  
                    can_go = False  
                    break                # 계속 탐색해도 된다면 continue  
                if can_go:  
                    continue  
                else:  
                    break  
            # 1 1 1 2 2 와 같이 낮은 곳에서 높은 곳으로 가는 경우  
            elif arr[i][j] - arr[i][j+1] == -1:  
                # arr[i][j]을 flag로 연속되는 개수가 L이상인지 체크해주기  
                flag = arr[i][j]  
                cnt = 0  
                idx = j  
                can_go = True  
                while cnt < L:  
                    # 범위 내이고 동일하다면 +1  
                    if idx >= 0:  
                        if arr[i][idx] == flag and visited[idx] == 0:  
                            visited[idx] = 1  
                            cnt += 1  
                            idx -= 1  
                            continue  
                    can_go = False  
                    break                if can_go:  
                    continue  
                else:  
                    break  
            else:  
                break  
        # for - else 문 사용하여 끝까지 온 경우 결과 += 1  
        else:  
            res+= 1  

    # 이번엔 열 체크  
    for j in range(N):  
        visited = [0] * N  
        for i in range(0, N-1):  
            if arr[i][j] == arr[i+1][j]:  
                continue  
            # 2 2 1 1 과 같이 높은 곳에서 낮은 곳으로 내려가는 경우  
            elif arr[i][j] - arr[i+1][j] == 1:  
                # arr[i+1][j]을 flag로 연속되는 개수가 L이상인지 체크해주기  
                flag = arr[i+1][j]  
                cnt = 0  
                idx = i+1  
                can_go = True  
                while cnt < L:  
                    # 범위 내이고 동일하다면 +1  
                    if idx < N:  
                        if arr[idx][j] == flag and visited[idx] == 0:  
                            visited[idx] = 1  
                            cnt += 1  
                            idx += 1  
                            continue  
                    can_go = False  
                    break                if can_go:  
                    continue  
                else:  
                    break  
            # 1 1 1 2 2 와 같이 낮은 곳에서 높은 곳으로 가는 경우  
            elif arr[i][j] - arr[i+1][j] == -1:  
                # arr[i][j]을 flag로 연속되는 개수가 L이상인지 체크해주기  
                flag = arr[i][j]  
                cnt = 0  
                idx = i  
                can_go = True  
                while cnt < L:  
                    # 범위 내이고 동일하다면 +1  
                    if idx >= 0:  
                        if arr[idx][j] == flag and visited[idx] == 0:  
                            visited[idx] = 1  
                            cnt += 1  
                            idx -= 1  
                            continue  
                    can_go = False  
                    break                if can_go:  
                    continue  
                else:  
                    break  
            else:  
                break  
        # for - else 문 사용하여 끝까지 온 경우 결과 += 1  
        else:  
            res+= 1  

    return res  

N, L = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  

result = check(0)  
print(result)

• 오랜만에 구현 문제를 풀었다.
• 처음부터 조건을 잘 정리해서 어떤 부분에서 문제가 생길지 파악하는 것이 전체 코드를 짜는 속도에 많은 영향을 주는 것 같다.
• 또한, 변수명 또한 명시적으로 적어주는 것이 디버깅할 때 많은 도움이 되었다.

---

pass 후 check 함수의 길이가 너무 길어 가독성을 위해 코드를 변경해주었다.

• check 함수의 인자로,
  • 해당 열 또는 행의 번호
  • 열인지 행인지를 0과 1로 구분하여 전달해주었다.
• 또한 연속된 숫자를 바로바로 cnt로 체크해주며 오르막을 만나는 경우 cnt가 L 이상이라면 가능하므로 경사로를 설치해준 후, 연속된 수의 개수를 다시 1로 변경해준다.
• 내리막을 만나는 경우 L개를 미리 빼서 음수로 만들어 주면서 연속된 수가 양수가 될 때까지 안 나온다면 return, 나온다면 경사로를 설치해준다.
  • 음수에서 양수가 된 후 다시 오르막을 만난다면 cnt가 L보다 작으므로 자동 return이 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, L = map(int ,input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  
result = 0  


def check(i, d):  
    global result  
    cnt = 1  # 연속된 칸의 개수  
    for j in range(N - 1):  

        val = arr[i][j + 1] - arr[i][j] if d else arr[j + 1][i] - arr[j][i]  
        if val == 0:  
            cnt += 1  
        elif val == 1 and cnt >= L:  # 오르막은 낮은 칸이 L개 이상인지 바로 확인 가능  
            cnt = 1  # L개 이상이면 연속된 칸의 개수를 1로 초기화  
        elif val == -1 and cnt >= 0:  # 내리막은 낮은 칸의 개수를 바로 확인 불가능  
            cnt = 1 - L  # 내리막 초반에 연속된 칸의 개수를 음수로 변경  
        else:  
            return  
    if cnt >= 0:  
        result += 1  



for i in range(N):  
    check(i, 1)  
    check(i, 0)  


print(result)