AtCoder: A - Range Flip Find Route - 파이썬(Python)

https://atcoder.jp/contests/agc043/tasks/agc043_a

A - Range Flip Find Route

<문제 선지>

H개의 행과 W개의 열로 구성된 정사각형이 있는 격자를 생각하자.
$(r, c)$는 위에서 r번째 행과 왼쪽에서 c번째 열에 있는 정사각형이다. 각 정사각형은 검은색 또는 흰색으로 되어있다.
다음 조건이 충족되는 경우에만 격자가 좋다고 한다.
$(1,1)$에서 오른쪽 또는 아래로 한 정사각형을 반복해서 이동하면 $(H,W)$에 도달할 수 있으며, 항상 흰색 정사각형에 있다. 격자가 좋은 경우 $(1,1)$과 $(H,W)$는 흰색이어야 한다.
우리는 아래 작업을 반복하여 격자를 좋은 것으로 만드는 것이다. 작업을 완료하는 데 필요한 최소 작업 수를 찾으라. 항상 유한한 수의 작업으로 작업을 완료할 수 있다는 것을 증명할 수 있다.

네 개의 정수 $r_0 ,c_0 ,r_1 ,c_1 (1≤r_0≤r_1≤H,1≤c_0≤c_1≤W)$를 선택한다.
각 쌍 $r,c (1≤r_0≤r_1≤H,1≤c_0≤c_1≤W)$에 대해 $(r,c)$의 색상을 반전한다. 즉, 흰색에서 검은색으로, 그 반대로 반전한다.

<접근 방법>

2차원 데이터를 1차원으로 구성해서 관찰하는 아이디어가 핵심인 문제라고 생각한다.
 
$(1,1)$에서 $(H,W)$로 가는 경로 $S=s_1s_2...s_{H+W}$를 생각해보자.
(길이가 H+W인 이유는 $H \times W$ 크기의 영역에서 $(1,1)$에서 $(H,W)$로 가는 최단 경로의 길이는 $H+W$이기 때문이다.)
 
예를 들어, H = 3, W = 3이고 전체 영역의 형태가 아래와 같이 구성되어 있다고 하자.
(편의상 검정을 노랑으로 색칠된 영역이라고 표현하겠다.)
 

H=3, W=3인 예시 영역

 
이때, 가능한 경로 S는 3가지가 존재한다.

가능한 전체 경로는 3가지이다.

 
여기서, "연속으로 색칠된 칸의 개수의 최솟값을 구하는 문제"로 해석할 수 있다는걸 알 수 있을 것이다.
위의 경우에는 답은 1이 될 것이다. (3개 모두 연속인 색칠된 칸의 개수는 1이므로)
 
이제 일반화된 경우에서의 정답은 어떻게 찾을 수 있을까?
 
아래와 같은 2차원 배열을 고려해보자. 여기서 $(1, 1)$에서 시작하여 $(3, 3)$까지 반복을 진행하자. $(1, 1)$의 경우, 만약 색이 칠해져 있다면 1로 변경한다. 예시 상황에서는 흰색이므로 그대로 둔다.

위 예시에서의 초기 상태

이제 $(1, 2)$에서 상황을 살펴보자. $(1, 2)$은 색이 칠해져 있다. 그리고 이전 칸을 확인해보자. 이전 칸의 후보로는 (0, 0)밖에 없다.(문제에서 정의된 이동은 "현재 칸에서 아래", "현재칸에서 오른쪽"으로 이동하는 연산이다. 여기서 $(0, 1)$를 목적지로하는 아래로 내려오는 이동은 없기 때문이다.)
이전 칸에서 1을 더한 값이 $(1, 2)$로 이동하는 최솟값이 되므로 1이 되어야 한다.
 
이제 해당 연산을 진행 도중인 (2, 2)에서의 계산 직전 상태를 살펴보자.

(2, 2)에서는 값이 어떻게 될까?

현재 $(1, 1)$은 색이 칠해져 있다. 이제 이전 칸의 후보들을 확인해보면 $(2, 1)$, $(1, 2)$가 있다. $(1, 2)$의 경우에는 색이 칠해진 상태가 유지가 되기때문에 1이 되어야 할 것이다. 그리고 $(2, 1)$의 경우에는 새롭게 색이 칠해진 칸이 추가되는 것이므로 1이 될 수 있다. 따라서 $(2, 2)$의 값은 1이 되어야 한다.
 
이와 같은 연산을 $(3, 3)$까지 진행하면 다음과 같다.

(3, 3)까지 진행한 결과

그러면 $(1, 1)$에서 $(3, 3)$ 까지 진행하는데 바꿔야 할 색의 최솟값은 1이 된다는 것을 알 수 있고, 실제로 일일히 확인해보아도 1이 답이된다는 것을 알 수 있다.
 
즉, 아래의 점화식을 이용하면 답을 도출할 수 있다.

(현재 칸에서의 최솟값) = min((위의 값에서 연산값), (왼쪽 값에서 연산값))

여기서 연산값 계산법은,
이전칸 = 흰색에서 현재칸 = 검은색일 경우, 현재칸 = 이전칸 + 1
그 외의 경우, 현재칸 = 이전칸

 

<소스 코드>

위의 접근법을 구현한 전체 소스 코드이다.
 
대상 칸이 영역에 포함되는지 여부를 확인하는 inner 함수를 구현하였고, 2중 for문을 이용하여 dp 배열을 갱신하면서 답을 찾는 로직을 구현하였다. 그리고 후보 좌표값을 기반으로 dp 배열 값을 갱신하여 dp 배열의 맨 마지막 값(즉, dp[h - 1][w - 1])을 출력하도록 하였다.

h, w = map(int, input().split())
arr = [list(input().strip()) for _ in range(h)]
dp = [[10001] * w for _ in range(h)]

mx = [-1, 0]
my = [0, -1]

def inner(h, w, i, j):
    return 0 <= i < h and 0 <= j < w

for i in range(h):
    for j in range(w):
        tmp = []
        for k in range(2):
            tx, ty = i + mx[k], j + my[k]
            if inner(h, w, tx, ty):
                tmp.append((tx, ty))
        
        if not tmp:
            dp[i][j] = 0 if arr[i][j] == '.' else 1
        else:
            for x, y in tmp:
                if arr[i][j] == '#' and arr[x][y]== '.':
                    dp[i][j] = min(dp[i][j], dp[x][y] + 1)
                else:
                    dp[i][j] = min(dp[i][j], dp[x][y])

print(dp[-1][-1])