BOJ 14276번 도로 건설

문제 링크

\(1\leq{N}\leq{30}\)

\(0\leq{M}\leq{30}\)

\(1\leq{K}\leq{8}\)

이 문제는 N개의 집이있을 때 집과 집을 잇는 M개의 양방향 도로를 설치 하는 문제이다.

A번 집과 B번 집을 잇는 도로를 설치하기 위해서는 0<|A-B| <= K 를 만족해야 한다.

두 집을 잇는 도로는 두개이상이어도 상관없다. 그리고 최종적으로 각각의 집과 인접한 도로의 개수가

짝수여야 한다. 이 때 도로를 건설하는 방법의 수를 구하는 문제이다.

이 문제를 풀기위해 필요한 것들이 여러가지가 있는데 첫번째로 이런 문제를 풀 때 유용한 테크닉이

중복되는 경우를 제거하기위해 A < B 인 A번집과 B번 집을 잇는 도로는 무조건 A 쪽에서만 이을 수 있다고 강제한다.

그리고 집은 1번부터 차례대로 봐준다고 강제한다. 그러면 중복이 일어날 일도 없고 편하다.

그럼 이 문제는 dp 로 풀 수가있다.  우선 부분문제를

dp[u][k][mask] : u번 집에서부터 k개의 도로를 건설 해야하며 u번 집을 포함하여 k+1개의 집에 대한 짝,홀 정보가

비트마스크로 mask 로 주어질 때 도로를 건설하는 경우의 수

로 잡으면 u==N 일 때 mask 가 0인지확인하여(짝수일 때가 0이라고 보면 K+1개의 비트가 모두 0이므로)

0또는 1을 리턴하면 될 것이다. 이렇게 하면 부분 문제의 수는 O(NM2^K) 가 된다.

그러면 각 부분 문제를 구하는 방법은 뭘까? 

우선 A번 집에서 다른 집으로 도로 건설한다고 하면 A+1번 도시에는 0~k개의 도로를 건설할 수가 있고 

A+2번 집에도 0~k 개의 도로를 건설할 수가 있고...... 정말 많은 경우의 수가 있고 반복문이 중첩이 되기때문에

구현도 복잡하다. 그렇기 때문에 애초에 부분 문제를 이렇게 세우면 이 문제를 풀기가 힘들어진다.

그럼 부분문제를 어떻게 바꿔야 할까?

dp[u][v][k][mask] : u번 집에서 v번 집부터 건설할지 봐줘야하며, k개의 도로를 건설해야하고 현재 집을 포함하여

K+1개의 집과 인접한 도로의 수의 짝홀정보 일 때 앞으로 도로를 건설하는 방법의 수

라고 부분문제를 정의하여 현재 u번 집에서 이어줄 집 번호를 부분문제에 명시하여 순서를 강제할 수가 있게된다.

그럼 매 순간 u번 집과 v번 집사이에 도로를 '하나 더' 건설할지 말지만 결정하면 된다. 그럼 하나의 부분문제를

구하는데 걸리는 시간복잡도는 O(1) 이 되는 것이다. 

도로를 건설한다면 go(u,v,k-1, nextmask) 이며(nextmask는 적절히 XOR하여 바꿔주면됨)

더이상 v에는 건설하지 않고 u에서 이어줄지 봐줄 집을 다음 집으로 넘어간다면 go(u,v+1,k,mask) 가 된다.

그리고 현재 u에서 다음 K개 노드까지만 봐주면되기 때문에 v-u > K 가 되는 순간 go(u+1,u+2,k,mask) 

와 같은 식으로 해주며, u를 다음 노드로 넘어간다면 더이상 u는 인접한 도로의 수가 변할 수 없게 된다.

왜냐하면 현재 보는 집보다 번호가 큰 집으로만 도로를 이을 수 있게 강제했기 때문이다. 그렇기 때문에

u를 다음 집으로 옮겨줄 때 u에 인접한 도로의 수가 홀수개라면 조건을 만족할 수 없으므로 0을 반환한다.

나머지는 그냥 u나 v가 N이 되었을 때에 대한 기저를 잘 해주고 나머지는 위에서 말한것처럼 mask 가 0인지

확인하고 그런걸 잘 하면된다.

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod = 1e9+7;
    const int inf = 0x3c3c3c3c;
    const long long infl = 0x3c3c3c3c3c3c3c3c;
 
    int N,M,K;
    ll dp[33][33][33][1<<9];
    ll go(int u, int v, int k, int mask){
        if(u == N || k == 0) return mask == 0 && k==0;
        if(v==N || v-u > K) {
            if(mask&1) return 0;
            return go(u+1,u+2,k,mask>>1);
        }
        ll& cache = dp[u][v][k][mask];
        if(cache != -1) return cache;
 
        cache = 0;
        cache = (cache + go(u,v+1,k,mask)) % mod;
        int nextmask = mask^(1<<(v-u));
        nextmask^=1;
        cache = (cache + go(u,v,k-1,nextmask)) % mod;
        return cache;
    }
    int main() {
        memset(dp,-1,sizeof(dp));
        scanf("%d%d%d",&N,&M,&K);
        printf("%lld",go(0,1,M,0));
        return 0;
    }