백준 14890번: 경사로 (Python)

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

14890번: 경사로

접근

일단 문제에서 예시를 보면, 가로로 먼저 계산할 때 경사로를 놓았던 위치는 세로 경로를 계산할 때에는 고려하지 않는다는 것을 알 수 있었다.
즉, 가로와 세로가 서로 영향을 주고 받지 않으므로, N * N matrix의 답을 계산할 때는 길이가 N인 리스트 2 * N 개만 계산하면 된다.
따라서 문제를 풀기 용이하게 하기 위해 solve 함수에서는 주어진 matrix를 쪼개서 리스트로 만들고, slope 함수에서는 이 리스트를 받아 이 길이 지나갈 수 있는 길인지 아닌지를 판단하여 리턴해주게 된다.

slope 함수에서는 해당 위치에 경사로가 놓아져있는지(경사로가 겹치는 것을 방지하기 위해) 확인하는 sloped 리스트를 새로 생성해주고, 경로 확인 중에 경사로를 놓을 때 표시해준다. 경로에서 0의 위치에서부터 탐색을 시작하며 다음과 같은 방식으로 탐색하게 된다.

1. 현재 위치와 +1 다음 위치와 높이가 같은 경우 한칸 진행
2. 현재 위치에서 다음 칸이 1만큼 더 낮을 경우, 현재 위치에서 앞쪽으로 경사로 길이만큼 탐색하여 경사로를 놓기에 적당할 경우 경사로 위치시키고 진행
3. 현재 위치에서 다음 칸이 1만큼 더 높을 경우, 현재 위치에서 뒤쪽으로 경사로 길이만큼 탐색하여 경사로를 놓기에 적당할 경우 경사로 위치시키고 진행

주의할 점은 앞 칸이 높아 뒤쪽으로 경사로 탐색 시에는 경사로가 이미 놓아져 있는지도 확인하여 탐색해야 한다.

코드

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


def solve(matrix):
    # 주어진 지도를 쪼개 경로 리스트로 만들어 지날 수 있는 길인지 판단하는 slope 함수에 전달
    cnt = 0
    for i in range(N):
        tmp = []
        for j in range(N):
            tmp.append(matrix[i][j])
        cnt += slope(tmp)
    for i in range(N):
        tmp = []
        for j in range(N):
            tmp.append(matrix[j][i])
        cnt += slope(tmp)
    return cnt


def slope(arr):
    sloped = [0] * N  # 경사로가 놓아질 경우 표시할 리스트
    now = 0
    floor = arr[now]  # 현재 위치의 높이
    flag = 1  # 탐색 중 더이상 진행 불가능할 경우 flag = 0
    while flag:
        if now == len(arr) - 1:
            # 끝까지 진행했을 경우, 지나갈 수 있는 길임을 1로 리턴
            return 1
        if arr[now + 1] == floor:
            # 현재 칸과 다음 칸의 높이가 같을 경우 1칸 진행
            now += 1
        elif now + 1 + L <= len(arr) and arr[now + L] == floor - 1:
            # 다음 칸이 더 낮을 경우 경사로를 놓기 적당한지 판단
            for i in range(L):
                if arr[now + 1 + i] != floor - 1:
                    # 현재 위치에서 경사로 길이만큼 탐색하여 경사로를 놓기 적당하지 않으면 flag = 0
                    flag = 0
                sloped[now + 1 + i] = 1  # 경사로 위치 표시
            now += L
            floor = arr[now]
        elif 0 <= now + 1 - L and arr[now + 1] == floor + 1:
            # 다음 칸의 높이가 더 높을 경우 뒤쪽으로 경사로 길이만큼 탐색하여 경사로를 놓기 적당한지 판단
            for i in range(L):
                # 평평하지 않거나, 이미 경사로가 놓아져 있을 경우 flag = 0
                if sloped[now - i] == 1:
                    flag = 0
                if arr[now - i] != floor:
                    flag = 0
                sloped[now - i] = 1
            now += 1
            floor = arr[now]
        else:
            flag = 0
    return 0


print(solve(matrix))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!