백준 1513 - 경로 찾기 (C++)

 

일단 메모이제이션을 통한 dp가 생각나긴 했는데 지금 방문가능한 오락실이 오름차순으로 허용되고, 또 방문 횟수에 따라 출력을 해야 하기 때문에 dp 배열을 몇 차원으로, 어떻게 관리를 해줘야 할지 고민을 많이 했다.

 

지금 그런데 좌표의 제한이 50이고 오락실 번호도 그리고 방문 가능한 횟수의 제한도 50이기 때문에 이 모든 정보(y, x, 방문 횟수, 이전에 방문한 오락실 번호)를 다 넣어서 4차원 배열을 사용해 보기로 했다. 어차피 뭐 다 해봤자 50^4=6250000 이니까...

 

int dp[54][54][54][54];  // y,x,최근에 방문한 오락실 번호,지난 오락실 수

 

일단 초기에 값을 받으며 dp 테이블을 세팅해 주는 작업을 진행하였다.

 

void init() {
  cin >> n >> m >> c;
  dp[1][1][0][0] = 1;
  for (int i = 1; i <= c; i++) {
    cin >> n1 >> n2;
    if (n1 == 1 && n2 == 1) {
      dp[1][1][0][0] = 0;
      dp[1][1][i][1] = 1;
    }
    a[n1][n2] = i;
  }
}

 

dp [1][1][0][0] = 1; 부분을 해석해 보면 (1,1) 시작점에서 최근에 방문한 오락실 번호가 0 + 지난 오락실 수가 0 즉, 아무것도 통과 안 한 상태는 경우의 수가 1이다. 그런데 문제를 잘 읽어보면 이런 조건이 있다.

 

오락실의 위치가 중복되는 경우는 없지만, 오락실의 위치가 (1,1) 또는 (N, M) 일 수도 있다.

 

이게 그 오락실이 (N, M) 일 때는 dp 테이블이 업데이트되는 과정에서 업데이트되기 때문에 상관없는데, 오락실이 (1,1)에 있을 때는 다시 우리가 수동으로 dp 테이블을 업데이트시켜줘야 한다. 왜냐하면 시작하자마자 오락실에 방문하게 되기 때문에 그렇다. 집이 오락실인가..?

 

어쨌든 만약에 오락실이 (1,1) 이면 dp [1][1][0][0]=0, 즉 출발지에 있는 오락실을 방문 안 하면서 출발하지는 못하므로 경우의 수를 0으로 업데이트시켜 주고, dp [1][1][i][1]=1, 즉 출발지에 있는 i번째 오락실을 방문하면서 방문한 횟수가 1인 경우의 수를 1로 업데이트시켜 준다.

 

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // 이미 (1,1)은 처리함
        if (i == 1 && j == 1) continue;

        if (a[i][j] > 0) {
            for (int l = 0; l <= a[i][j]; l++) {
                for (int k = 0; k <= l; k++) {
                    dp[i][j][a[i][j]][k + 1] +=
                        (dp[i - 1][j][l][k] + dp[i][j - 1][l][k]) % MOD;
                }
            }
        } else {
            for (int l = 0; l <= c; l++) {
                    for (int k = 0; k <= l; k++) {
                    	dp[i][j][l][k] += (dp[i - 1][j][l][k] + dp[i][j - 1][l][k]) % MOD;
                    }
            }
        }
    }
}

 

그다음에 그냥 시원하게 4중 for문을 돌려버린다. 여기서 신경써줘야 하는 부분은 크게 3개이다.

 

일단 첫 번째, 출발점인 (1,1)은 이미 처리해줬으므로 패스해준다.

 

두 번째, 현재 도착한 지점이 오락실인 경우, 일단 0부터 해당 오락실의 번호 그리고 오락실 번호 l에 대해 방문은 k번(0~l번) 방문 가능하므로 이렇게 2중 for문을 돌려준다. 이때 점화식은

 

dp[i][j][a[i][j]][k + 1] += (dp[i - 1][j][l][k] + dp[i][j - 1][l][k]) % MOD;

 

이렇고 해석해보자면 일단 (i,j)에 방문 가능한 경우의 수는 (i-1,j)+(i,j-1) 이므로 해당 위치에서 l번 오락실 방문 전 이미 k번 방문한 상태이므로 오락실 방문 후 k+1 지점에 업데이트 시켜준다.

 

세 번째, 현재 도착한 지점이 아무것도 아닌 경우, 위와 똑같이 2중 for문을 돌려주는데 이때 점화식은

 

dp[i][j][l][k] += (dp[i - 1][j][l][k] + dp[i][j - 1][l][k]) % MOD;

 

이렇다. 즉, 오락실에 도착하지 않았으므로 방문한 오락실과 방문 횟수에 영향을 주지 않는다. 그래서 저렇게만 점화식을 돌려주면 된다.

 

마지막은 출력 부분이다.

 

for (int i = 0; i <= c; i++) {
    int ret = 0;
    for (int j = 0; j <= c; j++) {
        ret += (dp[n][m][j][i] % MOD);
    }
    cout << ret % MOD << " ";
}
cout << "\n";

 

도착지점 (n,m)에서 각 오락실에 대해 거치는 횟수를 2중 for문으로 돌려 싹 출력해주면 된다.

 

오늘의 느낀점. 범위가 그렇게 안넓어서 4차원 dp로 조져줘도 됐었다. 범위를 잘 보자!