[백준 1577]-다리 개수 구하기(C++)

📕문제

세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자 형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.

따라서, 아래 그림과 같이 생겼다.

세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.

세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사 중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.

(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.

---

📕입력

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인공사 중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자연수이다. 셋째 줄부터 K개 줄에는 공사 중인 도로의 정보가 a b c d와 같이 주어진다. a와 c는 0보다 크거나 같고, N보다 작거나 같은 자연수이고, b와 d는 0보다 크거나 같고, M보다 작거나 같은 자연수이다. 그리고, (a, b)와 (c, d)의 거리는 항상 1이다.

---

📕출력

첫째 줄에 (0, 0)에서 (N, M)까지 가는 경우의 수를 출력한다. 이 값은 0보다 크거나 같고, 263-1보다 작거나 같은 자연수이다.

---

💡문제 해석

• 우리가 아는 행렬과 주어진 행렬의 그림은 다르다.
  • 이러한 행렬을 우리가 풀기 쉽게 좌표를 바꿔주는것이 1차 핵심이다.
• 입력값인 N,M,A,B,C,D 설명
  • 가로의 개수 N, 세로의 개수 M이지만 행렬상으로는 (M+1)*(N+1)의 크기를 설정해줘야 한다. 
  • A, B, C, D 중에서 [조건이 A>=C, B>=D]
    • 따라서 조건에 맞게 바꿔줘야 한다.
    • (A, B) -> (C, D)로 가는 길이 막혔다는 뜻이다.
  • 그리고 입력받은 좌표(즉 도착지에 해당하는 C, D) 값은 우리가 풀기 쉽게 만드는 행렬 값으로 바꿔줘야 하기 때문에 (C, D)->(D, C)로 바꿔준다.
• Road배열과 DP 배열
  • Road배열은 3차원 배열로 이루어짐. ( Road [i][j][k]))
    • i는 행, j는 열, k는 옵션(공사의 여부, 왼쪽, 아래쪽)
    • Road [i][j][0] = -1 --> 왼쪽에서 (i, j)로 가는 길이 막혔다는 뜻.
    • Road [i][j][1]=-1 --> 위쪽에서 (i, j)로 가는 길이 막혔다는 뜻.
  • DP [i][j]는 (i, j)로 가는 최소 경로의 개수이다.
    • 진행방향은 왼쪽과 위쪽에서 i, j로 갈 수 있다.
    • 보통의 경우 DP [i][j] = DP [i-1][j] (위쪽 방향) + DP [i][j-1](왼쪽 방향) 
    • 하지만 우리는 공사를 하는 도로를 생각해줘야 한다.
      • 공사를 한 경우는 위쪽에서 내려오는 경로와 왼쪽에서 오는 경로 2가지가 있다.
      • 여기서 생각해줘야 할게 더 이상 내려오지 못하는 경우와 왼쪽에서 오지 못하는 경우도 생각해줘야 한다.
        • i-1>=0(아래에서 내려오지 못하는 경우== 즉 맨 위인 경우). j-1>=0(왼쪼겡서 오지 못하는 경우 == 즉 맨 왼쪽인 경우)
  • 최종적으로 우리가 구할 값은 DP [m][n]이 될 것이다.

💡코드

/*
행렬을 뒤집어서 출발점을 0,0 -> N,M으로 하되 구멍뚫린 도로의 위치를 잘 특정해서 넣어줘야함.
구멍 좌표는 x,y를 서로 바꿔주면됨.
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long int n, m, T, finishx, finishy, startx, starty;
int main()
{
    cin >> n >> m;
    int road[m + 1][n + 1][2];
    long long int DP[m + 1][n + 1];
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            DP[i][j] = 0;
            for (int k = 0; k < 2; k++)
            {
                road[i][j][k] = 0;
            }
        }
    }
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        //행렬을 회전시킬거임 그러면 x,y 좌표는 반대가 되용.
        //(a,b)->(c,d)
        // DP에서 3차원 좌표상 0은 막힌 곳 없다. 1은 왼쪽으로 막힘. 2는 아래로 가는 길 막힘.
        if (a == c)
        { // x좌표가 같다면 아래으로 가는 길 막힘
            if (b > d)
                road[b][c][1] = -1;
            else
                road[d][c][1] = -1;
        }
        if (b == d)
        { // y좌표가 같다면 왼쪽로 가는 길 막힘
            if (a > c)
                road[d][a][0] = -1;
            else
                road[d][c][0] = -1;
        }
    }

    // DP[i][j] =DP[i-1][j]+DP[i][j-1]이 최소의 경로겟지?
    //근데 만약 그 값보다 크다면? 그때는 최적의 경로가 아니야
    DP[0][0] = 1;
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i - 1 >= 0 && road[i][j][1] != -1) //아래로 가는 길안막혀잇을떄)
            {
                DP[i][j] = DP[i][j] + DP[i - 1][j];
            }
            if (j - 1 >= 0 && road[i][j][0] != -1) //왼쪽 안막혀잇을때)
            {
                DP[i][j] = DP[i][j] + DP[i][j - 1];
            }
        }
    }
    cout << DP[m][n];
}

---

✔느낀 점

• 내가 풀었던 DP 중에서 가장 어려웠다.
• 알고리즘 적으로는 충분히 이해가 갔지만, 예외 처리와 그 코드로 구현하는 것이 생각보다 까다로웠다.
• 3차원 배열로 설정해서 방향을 넣어주는 것이 신의 한수인 것 같다.
• 그리고 vector를 쓰지 않는 경우 초기화를 잘하자.. 제발!! (쓰레기 값이 들어가서 몇몇 테케에서 틀렸음).