[Python/파이썬] 백준 11909번 배열 탈출

11909번: 배열 탈출

 

문제

상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다.

배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다! 최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다.

[그림 1] n=4라면 상수는 A[1,1]에 있고, 출구는 A[4][4]에 있습니다.

상수는 가능한 한 빨리 출구인 A[n][n]에 도달하고자 합니다. 상수가 A[i][j]에 있다고 가정했을 때, 상수는 최단 경로로 이동하기 위해 아래와 같은 조건을 만족하며 이동합니다.

1. 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
2. i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
3. 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
4. i=j=n인 경우 바로 출구로 갑니다.

[그림 2] n=5라고 가정합시다. (ㄱ)는 1번 조건을 만족하고, (ㄴ)는 2번 조건을 만족하며, (ㄷ)는 3번 조건을 만족합니다.

그러나 건너갈 때에도 제약이 따릅니다. 상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]를 만족해야 합니다. 상수는 왜인지 이런 조건을 만족하면서 이동할 수 없을 것 같았습니다. 다행히도, 승현이가 상수를 배열에 가둬버리기 전에, 상수는 배열의 각 원소에 버튼을 만들어 놓아서, 이 버튼을 누르면 해당 원소의 값이 1 증가하도록 했습니다. (물론 상수는 자신이 위치해 있는 원소의 버튼만 누를 수 있습니다.) 이 버튼 덕분에, 상수는 항상 배열을 탈출할 수 있습니다!

[그림 3] n=2라고 가정합시다. A[1][1]=5>A[1][2]=2이므로, 상수는 A[1][1]에서 A[1][2]로 건너갈 수 있습니다. 상수가 A[1][1]에서 A[2][1]로 건너가려면, A[1][1]에 있는 버튼을 두 번 눌러 A[1][1]의 값을 7로 만들면 됩니다.

하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다. 상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하고자 합니다. 상수를 도와주세요.

 

입력

첫 번째 줄에 n이 주어집니다. (n ≤ 2,222)

다음에 n개 줄이 주어집니다. 이 중 i(1≤i≤n)번째 줄에는 n개의 수 A[i][1],A[i][2],⋯,A[i][n−1],A[i][n]이 공백을 사이로 두고 차례대로 주어집니다.

출력

첫 번째 줄에 상수가 배열을 탈출하기 위해 들여야 할 최소 비용(원 단위)을 출력합니다.

코드

import sys
input = sys.stdin.readline

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

cost = [[int(1e9)]*n for _ in range(n)]
cost[0][0] = 0
for i in range(n):
    for j in range(n):
        for a, b in [(0, 1), (1, 0)]:
            nr, nc = i+a, j+b
            if nr >= n or nc >= n:
                continue
            next_cost = cost[i][j]+(0 if arr[i][j] > arr[nr][nc] else arr[nr][nc]-arr[i][j]+1)
            if next_cost < cost[nr][nc]:
                cost[nr][nc] = next_cost
print(cost[n-1][n-1])

 

2차원 배열 cost에 (i,j)칸에 가는데 필요한 최소 비용을 저장한다.

현재 칸에서 다음에 갈 수 있는 칸 (nr, nc)에 비용을 저장하는데 이때 버튼을 누르지 않아도 이동 가능한 칸이면 0, 버튼을 눌러야 한다면 최소 횟수인 arr[nr][nc]-arr[i][j]+1을 cost[i][j]에 더한 값이 비용(next_cost)이다. 원래 cost[nr][nc]에 저장된 값보다 이번에 구한 비용(next_cost)이 더 작다면 이번에 구한 비용을 cost[nr][nc]에 저장해주는데 이때 min 함수를 이용했더니 시간초과가 발생해서 if문을 이용하였더니 시간 초과가 해결됐다.

 

처음에는 bfs로 풀으려고 했는데 시간 초과가 나왔다. 생각해보니 이동은 위 또는 아래로만 가능하기 때문에 왔던 길로 되돌아갈 가능성은 없기 때문에 굳이 bfs로 풀며 방문처리하고 그럴 필요가 없었다.