어떤 점 (x, y)에서 도달가능한 모든 지점들이 포함된 집합을 p(x, y)라 할게요.
일단 장애물이 없는 상황부터 생각해봅시다.
|p(x+1, y) - p(x+1, y+1)|는 (x,y)에서 꼭 오른쪽으로 진행해야만 도달할 수 있는 지점의 수입니다.
|p(x, y+1) - p(x+1, y+1)|는 아래쪽으로고요.
이 둘을 곱하면 독립쌍의 수가 됩니다.
x, y < N - 1인 모든 점에 대하여 독립쌍의 수를 구하고 합하면 정답입니다.
p(x,y)는 dp를 사용하면 구할 수 있습니다.
dp[x][y] = dp[x+1][y] + dp[x][y+1] - dp[x+1][y+1]을 하면 됩니다.
물론 dp배열은 오른쪽 아래부터 왼쪽 위로 순서대로 값을 계산해줘야합니다.
이제 장애물이 있는 상황을 생각해봅시다.
아래 그림을 보자면 u=(x,y)라 할 때 빨간색 빗금이 p(x,y+1), 파란색 빗금이 p(x+1,y)입니다.
u에서 시작하는 경로 중 독립쌍의 수를 세려면
저 빨간색과 파란색 빗금이 겹치는 지점의 수를 찾아서 빼줘야합니다.
아까 장애물이 없었을 때의 p(x+1,y+1)을 빼줬던 것처럼 빼야하는데 u의 오른쪽 아래는 벽이 있어서 저렇게 겹치는 부분이 멀리 가있는 것입니다.
저 값을 u의 오른쪽 아래로 직접 운반해주면 됩니다.
dp배열을 순회할 때 현재 위치에 벽이 있을 때,
오른쪽과 아래쪽에 둘 다 벽이 없으면 k의 왼쪽 위 지점이라는 뜻입니다. |p(k)|의 값을 넣어줍니다.
그 외의 경우 오른쪽, 아래쪽, 대각선 지점 중 벽이 있는 곳을 찾아서 값을 복사해줍니다.
그럼 벽이 모여있는 뭉탱이가 다 같은 k값을 가지게 됩니다.
그래서 u에서도 독립쌍의 수를 계산할 때 (x+1,y+1)에 벽이 있더라도 dp[x][y] = dp[x+1][y] + dp[x][y+1] - dp[x+1][y+1]로 계산하면 됩니다.
되게 쉽게 푼 거 같고 풀이 공유하고 싶어서 공들여 썼습니다... 읽어주셔서 감사합니다.
개고수
오 저도 그렇게 풀었습니다. 차이점이라면 저는 (N, N)이 아니라 (0, 0)에서부터 시작을 해서, (0, 0)의 값을 통해 (0, 1)과 (1, 0)의 값을, 그리고 그와 (0, 0)을 통해 (1, 1)의 값을, 그리고 그러한 과정을 반복하여 모든 비독립쌍의 수를 구했고, 그 과정에서 장애물은 개별적으로 처리해 만약 그 위치를 (a, b)라 할 때 (a - 1, b) 혹은 (a, b - 1)에 장애물이 있는 경우 그 값을 그대로 가져오게 하였고, 만약 둘 모두 장애물이 있을 경우 (a - 1, b - 1)의 값을 가져오게 하였습니다.
왜냐면 문제에서 전제하기를 모든 장애물이 아닌 셀은 그를 지나는 적법한 경로가 존재하고, 그러기 위해서는 (a, b), (a - 1, b), (a, b - 1)이 모두 장애물이며 (a - 1, b - 1)이 장애물이 아닌 경우는 존재할 수 없기 때문입니다.
그리고 모든 쌍의 수는 그냥 n choose 2 이항계수 계산과 동일한 값을 가지는 n * (n - 1) / 2로 계산하여 구한 후 그 수에서 비독립쌍의 수를 감해 독립쌍의 수를 구했네요.
오 기본 원리는 완전 똑같네요. 풀이 잘 읽었습니다. 감사합니다.
저도 비슷한 풀이를 보아 반가웠습니다!
오 저도 이런식으로 접근해보다가 장애물 있는 상황을 결국 해결은 못했는데 잘못된 접근은 아니었군요 잘 보고 갑니다~
나도 저렇게 풀었는데 저 벽있는 곳을 그냥 bfs로 사전처리해서 구해놓아서 각 벽마다 그 벽이 포함된 벽뭉치의 왼쪽 위 부분을 저장했는데 생각해보니까 모든 벽마다 왼쪽 위 저장할 필요 없이 맨 오른아래쪽 벽에 대해서만 왼쪽 위 벽 정보가 필요한거구나 아하
이게 출제측에서 모범으로 본 답이라는 설이 있어요