백준 17070: 파이프 옮기기 1

문제 요약

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

파이프는 회전시킬 수 있으며, 가로, 세로, 왼쪽위-오른쪽아래 대각선의 3가지 방향이 가능하다.

가로 파이프에는 가로 및 대각선 파이프를, 세로 파이프에는 세로 및 대각선 파이프를, 대각선 파이프에는 모든 파이프만을 연결할 수 있다.
파이프는 항상 빈 칸만 차지해야 한다.

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

문제 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색

문제 풀이

3차원 DP문제이다. 탑다운 방식으로 해결했는데, 함수의 매개변수로 현재 파이프의 모양을 나타내는 flag변수를 두었다. 현재 파이프 모양에 따라 재귀호출 될 파이프의 모양이 정해지게 된다. 세로일 때는 세로 및 대각선, 가로일 때는 가로 및 대각선, 대각선일 때는 모든 경우를 누적하여 반환해주었다.
(n, n)에는 가로, 세로, 대각선 모든 모양의 파이프가 저장될 수 있으므로 모든 경우를 호출시켜서 누적하여 출력하였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int n, ary[16][16], dp[16][16][3];

int sol(int y, int x, int flag) // flag : 0세로, 1가로, 2대각선
{
    if (y == 0 && x == 1 && flag != 0) return 1;
    else if (x <= 1) return 0;
    if (dp[y][x][flag] != -1) return dp[y][x][flag];
    dp[y][x][flag] = 0;
    if (flag == 0) {
        if (y > 0) {
            if (!ary[y - 1][x])
                dp[y][x][flag] += sol(y - 1, x, 0);
            if (!ary[y - 1][x - 1] && !ary[y][x - 1] && !ary[y - 1][x])
                dp[y][x][flag] += sol(y - 1, x - 1, 2);
        }
    }
    else if (flag == 1) {
        if (!ary[y][x - 1])
            dp[y][x][flag] += sol(y, x - 1, 1);
        if (y > 0) {
            if(!ary[y - 1][x - 1] && !ary[y][x - 1] && !ary[y - 1][x])
                dp[y][x][flag] += sol(y - 1, x - 1, 2);
        }
    }
    else {
        if (!ary[y][x - 1])
            dp[y][x][flag] += sol(y, x - 1, 1);
        if (y > 0) {
            if (!ary[y - 1][x])
                dp[y][x][flag] += sol(y - 1, x, 0);
            if (!ary[y - 1][x - 1] && !ary[y][x - 1] && !ary[y - 1][x])
                dp[y][x][flag] += sol(y - 1, x - 1, 2);
        }
    }
    return dp[y][x][flag];
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &ary[i][j]);
    
    int res = 0;
    if (!ary[n - 1][n - 1]) {
        if (!ary[n - 2][n - 1])
            res += sol(n - 2, n - 1, 0);
        if (!ary[n - 1][n - 2])
            res += sol(n - 1, n - 2, 1);
        if (!ary[n - 2][n - 2] && !ary[n - 1][n - 2] && !ary[n - 2][n - 1])
            res += sol(n - 2, n - 2, 2);
    }
    cout << res;

    return 0;
}