BOJ 16121(사무실 이전)풀이

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

16121번: 사무실 이전

티어에 비해? 간단했지만 구현 때문에 말아먹은 문제이다.

인접한 두 점의 거리는 모두 1이기 때문에 제곱수의 규칙을 알면 쉽게 할 수 있다.

1부터 5까지만 표시해보자면 1^2=1,2^2=4,3^2=9,4^2=16,5^2=25

나열하면 1 4 9 16 25 이렇게 나오는 걸 알 수 있다. 여기서 규칙을 찾아보면 3,5,7,9 씩 커진다. 즉 전에 커진 수+2만큼을 전수에 더하면 (n+1)^2를 구할 수 있는 것이다.

그렇기 때문에 전 노드에서 더해야 되는 수+2만큼을 전수에 더해주면 된다.

하지만 이렇게 했을 경우 문제가 생긴다. 만약 한 노드의 자식들한테 사람이 있는 점이 2개 이상 있다면 어떻게 해야 될까?

이것도 생각보다 간단하다 여러 점들이 있으니 점 개수*2만큼을 더하고 전 값들의 합에 더해주면 된다.

 

이런 그래프가 있다고 하자

시작은 1로 하겠다

A, B, F에 사람이 있다고 할 때 C에는 A에서 C를 연결하려면 전 값+1을 더해줘야 하고 B에서 C를 연결하려면 전 값+1을 해줘야 한다. A, B 모두 전 값 즉 A, C를 부모로 하는 모든 노드들 중 사람이 있는 곳과의 거리 제곱은 둘 다 0이고 처음에는 개수*2가 아닌 1을 더해줘야 하므로 1씩 더해 준다 그러면 C의 값은 2가 되고 C에서 C의 부모 노드들이 더해야 되는 값은 6이 된다. 이유는 C에서 1을 더했기 때문에 그 위 노드들은 1+노드 개수*2*깊이 차이만큼을 더해줘야 되고 바로 위 부모 노드는 노드 개수*2만큼을 더해줘야 하기 때문에 2*2=4를 2에 더해준다. 그 값을 D에서 불러와 더하고 계속 2*2를 더해주는 것이다. 이 방식을 계속하다 보면

A=1, B=1, C=2, D=8, E=19, G=36 이렇게 나오게 된다. 하지만 아직 끝이 아니다 아직 X노드를 부모로 하는 노드들 중 사람이 있는 곳과의 거리 제곱의 합만 구해 줬기 때문에 나머지 점들과의 거리 제곱도 구해줘야 한다.

nd f(ll x,ll lt){
    ll ty=0,zc=0,cnt=0,v=0;
    for(int i=0;i<graph[x].size();i++){
        ll next=graph[x][i];
        if(next!=lt){ty=1;nd gh=f(next,x);zc+=gh.v+gh.cnt*2;cnt+=gh.cnt;v+=gh.v+dp[next];}
    }
    if(ty==0){
        if(st[x]==1){
            dp[x]=0;nm[x]={1,1};return nm[x];
        }else{dp[x]=0;nm[x]={0,0};return nm[x];}
    }
    dp[x]=v%mod;
    if(st[x]==0){nm[x]={cnt,zc};return nm[x];
    }else{nm[x]={cnt+1,zc+1};return nm[x];}
}

이렇게 구현해 줄 수 있다.

 

 

여기서부턴 구현이 좀 짜증 난다.(실제로 여기서 맞왜틀을 2일 동안 함)

나머지 노드들과의 거리를 구하려면 위에서 구했던 값들을 이용해주면 된다. 위 방식대로라면 D는 G값에서 D값이랑 D와 바로 위 부모랑 연결할 때 더한 간선 값을 빼주고 ((E에서 사람이 있는 점 개수)-(D에서 사람이 있는 점 개수))*2+나머지 점들과의 더해야 되는 값만큼을 더해주면 더해야 되는 값을 구할 수 있다. 그다음에 부모 노드 값을 더해주면 된다.

이제 이걸 어떻게 구현하냐 인데 처음에 

"바로 위 부모랑 연결할 때 더한 간선 값을 빼주고"

이것은 x를 부모 next를 자식이라고 했을 때

dp [x]-dp [next]-두 점을 연결할 때 추가한 값

이 되고 

"((E에서 사람이 있는 점 개수)-(D에서 사람이 있는 점 개수))*2"

(이것은 x점를 부모로 하는 점들 중 사람이 있는 개수-next 점을 부모로 하는 점들 중 사람이 있는 개수)*2를 해주면 되는 것이다.

위에서 개수를 이미 저장해줬으니 바로 구해줄 수 있다.

마지막으로

"나머지 점들과의 더해야 되는 값"

은 x가 next였을 때 

"((G에서 사람이 있는 점 개수)-(E에서 사람이 있는 점 개수))*2+나머지 점들과의 더해야 되는 값"을 더해주면 된다.

바로 위 노드와의 거리 값은 위에서 구했고 나머지 점들 간의 거리는 

"dp [x]-dp [next]-두 점을 연결할 때 추가한 값" 말고 더하는 값을 저장해주면 되고 이때도 +부모 값을 저장해줘야 한다

자식과의 거리를 구할 때는 +자식 값을 했지만 여기선 반대로 위에서부터 처리하고 있으니 +부모 값을 해줘야 한다

이렇게 두 개의 값을 구해줬으면 

"사무실을 옮기려는 후보 지하철역" 값의 위치에 있는 위, 아래 값을 더해주면 된다.

이렇게 하면 좋겠지만 mod가 있으니 모든 곳에 mod를 넣어주도록 하자

void uo(ll x,ll lt,ll hj){
    for(int i=0;i<graph[x].size();i++){
        ll next=graph[x][i];
        if(next!=lt){
            //if(hj==1){
            dp1[next]=((dp[x]-dp[next]-nm[next].v)+(nm[x].v-(nm[next].v+nm[next].cnt*2)))%mod+ch[x]%mod+dp1[x]%mod;
            ch[next]=(nm[x].v-(nm[next].v+nm[next].cnt*2))+(b-nm[next].cnt)*2+ch[x];
            dp1[next]%=mod;
            ch[next]%=mod;
            uo(next,x,hj);
            //}else{dp1[next]=0;ch[next]=0;uo(next,x,hj);}
        }
    }
}

이렇게 구현해 줄 수 있다.