[알고리즘 문제 풀기] 파이프 옮기기 1(17070)

1. 문제 풀이 아이디어

• mm[i, j, k]에 (i, j)에서 방향 k(가로, 세로, 대각선)로 도달하는 경우의 수를 저장하고, 이동 가능 여부를 확인하며 갱신하여 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int[,] map = new int[n, n];

    for (int i = 0; i < n; i++)
    {
        string[] split = sr.ReadLine().Split();
        for (int j = 0; j < n; j++)
        {
            map[i, j] = int.Parse(split[j]);
        }
    }
    int[,,] mm = new int[n, n, 3];
    if (map[0, 2] == 0) mm[0, 2, 0]++;
    if (map[0, 2] == 0 && map[1, 1] == 0 && map[1, 2] == 0) mm[1, 2, 2]++;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mm[i, j, 0] > 0)
            {
                if (ChkHor(i, j)) mm[i, j + 1, 0] += mm[i, j, 0];
                if (ChkDiag(i, j)) mm[i + 1, j + 1, 2] += mm[i, j, 0];
            }
            if (mm[i, j, 1] > 0)
            {
                if (ChkVer(i, j)) mm[i + 1, j, 1] += mm[i, j, 1];
                if (ChkDiag(i, j)) mm[i + 1, j + 1, 2] += mm[i, j, 1];
            }
            if (mm[i, j, 2] > 0)
            {
                if (ChkHor(i, j)) mm[i, j + 1, 0] += mm[i, j, 2];
                if (ChkVer(i, j)) mm[i + 1, j, 1] += mm[i, j, 2];
                if (ChkDiag(i, j)) mm[i + 1, j + 1, 2] += mm[i, j, 2];
            }
        }
    }
    sw.WriteLine(mm[n - 1, n - 1, 0] + mm[n - 1, n - 1, 1] + mm[n - 1, n - 1, 2]);
    bool ChkHor(int i, int j)
    {
        return j + 1 < n && map[i, j + 1] == 0;
    }
    bool ChkVer(int i, int j)
    {
        return i + 1 < n && map[i + 1, j] == 0;
    }
    bool ChkDiag(int i, int j)
    {
        return j + 1 < n && i + 1 < n && map[i, j + 1] == 0 && map[i + 1, j] == 0 && map[i + 1, j + 1] == 0;
    }
}

3. 정리

• mm[i, j, k]를 사용하여 (i, j)에서 k 방향으로 도달하는 방법의 수를 저장한다.

• 초기 상태에서 (0,1)에서 가로 방향과 세로 방향이 가능한 경우를 설정한다.

• (i, j)에서 가로, 세로, 대각선 방향으로 이동 가능 여부를 체크하고 dp를 갱신한다.

• 최종적으로 (n-1, n-1)에서 모든 방향의 합을 출력한다.