[백준] 1577 - 도로의 개수 (C++)

https://www.acmicpc.net/problem/1577

아래 그림처럼 가로 크기가 N이고 세로 크기가 M인 도시가 있다. 도시에는 중간중간 공사 중인 도로가 있고, 이 도로는 지나갈 수 없다. 세준이는 (0, 0)에 있는 집에서 (N, M)에 있는 학교까지 최단 거리(N + M)로 이동하려고 할 때, 서로 다른 경로의 경우의 수를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N, M ≤ 100
• 0 ≤ K ≤ 50
• 0 ≤ a, c ≤ N
• 0 ≤ b, d ≤ M
• (a, b)와 (c, d)의 거리 = 1
• 0 ≤  (0, 0)에서 (N, M)까지 가는 경우의 수 ≤ 2⁶³ - 1

 

확률 문제에서 자주 봤던 경우의 수를 구하는 문제와 비슷하다.

 

(i, j)까지 도달할 수 있는 경우의 수는 (i-1, j)와 (i, j-1)까지 도달할 수 있는 경우의 수를 더해서 구할 수 있다. 지나갈 수 없는 도로는 pair<pair<int,int>, pair<int,int>>로 저장하고, 경우의 수에 더하기 전 해당 도로를 지나갈 수 있는지 확인하고 지나갈 수 없다면 0을 더해야 한다. 

 

서로 다른 경로의 경우의 수는 int 범위를 넘기 때문에 long long int로 선언해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, K 입력받기
2. 공사 중인 도로 정보 입력받기 (a, b, c, d → K개)
3. dp 배열의 (0, 0)을 1로 초기화하고, (0, 0)부터 (0, M)까지, (0, 0)부터 (N, 0)까지 dp 배열을 초기화하기
   1. 1로 초기화하고, 공사 중인 도로를 만나면 지나갈 수 없으므로 0으로 초기화
4. (1, 1)부터 (N, M)까지 dp 배열 갱신하기
5. dp[N][M] 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#define pii pair<int,int>
using namespace std;

long long int n,m,k,a,b,c,d,dp[101][101]={1};
vector<pair<pii,pii>> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    for (int i=0; i<k; i++) {
        cin >> a >> b >> c >> d;
        v.push_back({{a,b},{c,d}});
    }

    int tmp=1;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<k; j++) {
            a = v[j].first.first, b = v[j].first.second, c = v[j].second.first, d = v[j].second.second;
            if (a==i-1 && b==0 && c==i && d==0 || a==i && b==0 && c==i-1 && d==0) {
                tmp=0;
                break;
            }
        }
        dp[i][0] = tmp;
    }
    tmp=1;
    for (int i=1; i<=m; i++) {
        for (int j=0; j<k; j++) {
            a = v[j].first.first, b = v[j].first.second, c = v[j].second.first, d = v[j].second.second;
            if (a==0 && b==i-1 && c==0 && d==i || a==0 && b==i && c==0 && d==i-1) {
                tmp=0;
                break;
            }
        }
        dp[0][i] = tmp;
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            bool x=false, y=false;
            for (int l=0; l<k; l++) {
                a = v[l].first.first, b = v[l].first.second, c = v[l].second.first, d = v[l].second.second;
                if (a==i-1 && b==j && c==i && d==j || a==i && b==j && c==i-1 && d==j) x = true;
                if (a==i && b==j-1 && c==i && d==j || a==i && b==j && c==i && d==j-1) y = true;
            }
            if (!x) dp[i][j] += dp[i-1][j];
            if (!y) dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[n][m];
}