[백준 BOJ] 17070. 파이프 옮기기 1
22 Aug 2021난이도
Gold V
문제 풀이
딱 문제를 봤을 때는 DFS나 BFS를 활용해 풀 수 있다고 생각했다. 실제로도 백 트래킹과 그래프 탐색 알고리즘을 활용하면 길지 않은 시간에 이 문제가 풀린다. 그래서 처음에는 BFS를 활용해서 풀려고 시도했는데.. 구현력이 좀 딸렸던건지 잘 안 풀려서 방향을 틀었다. 내가 선택한 방법은 3차원 배열을 사용하는 DP이다. 먼저, 파이프가 가질 수 있는 상태를 먼저 살펴보자.
파이프가 세로로 놓여진 경우 이전의 상태는 두가지 경우가 있다. 첫번째는 세로 상태로 놓여졌던 경우, 두번째는 대각 상태로 놓여졌던 경우이다. 그럼, 그 두가지가 되기 위한 경우의 수를 더하면 지금 세로로 놓여진 상태의 경우의 수가 되지 않겠는가? 이런식으로 나머지 경우들도 살펴보자.
다음으론 가로로 놓여진 경우이다. 같은 방법으로, 이전의 상태는 가로와 대각이 가능하다. 즉, 가로로 놓여진 경우의 수 = (이전)가로로 놓여진 경우의 수 + (이전)대각으로 놓여진 경우의 수 인 셈이다.
마지막으로, 가장 까다로운 부분인 대각으로 놓여진 경우이다. 앞의 두 경우들과 다르게 점유하는 영역이 더 넓기에 그 부분까지도 코드에 체크해줘야 한다. 아무튼 체크했다고 생각해보면, 대각 = (이전)(세로 + 대각 + 가로) 인 셈이다. 이걸 파악하고 나면, 어떻게 DP를 해야할지 감이 오지 않는가?
먼저 파이프의 상태(세로, 대각, 가로)를 숫자로 표현하자. 나는 세로-대각-가로를 각각 0, 1, 2로 표현하기로 했다. 그리고 DP배열의 정의를 다음과 같이 해보자.
\(\small dp[k][y][x] =\) 좌표 (x, y)에서 k상태로 놓여지는 파이프의 경우의 수.
그럼, 위에서 발견했던 사실을 종합하여 다음과 같은 점화식을 생각해 볼 수 있다.
\[\small dp[0][y][x] = dp[0][y - 1][x] + dp[1][y - 1][x]\] \[\small dp[1][y][x] = dp[0][y - 1][x-1] + dp[1][y - 1][x - 1] + dp[2][y - 1][x-1]\] \[\small dp[2][y][x] = dp[1][y][x - 1] + dp[2][y][x - 1]\]
x와 y를 늘려가며 각 좌표마다 dp 배열값을 구하는 식으로 코드를 짜면, \(\scriptsize O(N ^ {2})\)에 문제를 해결할 수 있다. 나는 그 코드를 다음과 같이 짜 보았다.
vector<vector<vector<int>>> dp(3, vector<vector<int>>(N, vector<int>(N))); //dp[status][y][x]
dp[2][0][1] = 1; //base
for(int y = 0; y < N; ++y) {
for(int x = 0; x < N; ++x) {
for(int k = 0; k < 3; ++k) {
if(k == 0 && isNotWall(x, y) && isValid(x, y - 1))
dp[0][y][x] = dp[0][y - 1][x] + dp[1][y - 1][x] ;
else if(k == 1 && isNotWall(x, y) && isNotWall(x - 1, y) && isNotWall(x, y - 1) && isValid(x - 1, y - 1))
dp[1][y][x] = dp[0][y - 1][x-1] + dp[1][y - 1][x - 1] + dp[2][y - 1][x-1];
else if(k == 2 && isNotWall(x, y) && isValid(x - 1, y)) {
if(x == 1 && y == 0) continue; //skip base
dp[2][y][x] = dp[1][y][x - 1] + dp[2][y][x - 1];
}
}
}
}
코드를 보면 \(\scriptsize dp[2][0][1] = 1\)로 먼저 초기화하고 시작한다. 왜냐면, 시작이 (0, 1)에서 가로 상태로 시작하기 때문이다. 그 경우가 한가지 이므로 1로 초기화 해주고 y와 x를 순차적으로 늘려가며 각 상태에 대한 dp값들을 업데이트 한다(이때, k == 2에서 (1, 0)부분을 스킵하는데, 그게 기저 사례이기 때문에 스킵해준다..). isNotWall함수는 해당 좌표가 유효하고, 벽이 아닌지 체크하는 함수이고, isValid 함수는 해당 좌표가 유효한지 검사한다. 나는 이걸 대충 아래처럼 짰다.
bool isNotWall(int x, int y) {
if(x < 0 || x >= N || y < 0 || y >= N) return false;
if(map[y][x] == 1) return false;
else return true;
}
bool isValid(int x, int y) {
if(0 <= x && x < N && 0 <= y && y < N) return true;
else return false;
}
주목해서 봐야할 부분은 k == 1인 부분 즉, 대각 상태로 놓여진것을 계산하는 부분이다. 파이프가 놓여진 2 x 2 영역에는 벽이 없어야하고 좌표가 유효해야함을 유의하며 코드를 짜야 제대로 된 결과가 나온다.
이렇게 반복문을 모두 수행하고 나서, 답은 \(\scriptsize dp[0][N - 1][N - 1] + dp[1][N - 1][N - 1] + dp[2][N - 1][N - 1]\) 이므로 이것을 출력해주면 끝이다. 3차원 배열을 이용해 dp를 해보는것은 처음이었는데.. 하위 차원 dp랑 크게 다르진 않았다. 문제가 실수하기 좋은 요소를 포함하고 있기에 그걸 신경쓰는게 좀 까다로운 문제가 아니였을까?