백준 21606: 아침 산책

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

21606번: 아침 산책

 

108점 풀이

처음에 생각했던 풀이는 그냥 모든 '실내'에 대해서 dfs를 돌려서 계산을 하는 것이었습니다. 구현을 해놓고 보니 시간복잡도가 $O(N^2)$으로 예상이 되어 마지막 서브태스크를 통과하지 못할 것 같다고 생각했었고, 실제로도 그랬습니다.

108점 받은 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int n;
long long cnt;
bool visited[200001];
string s;
vector<int> adj[200001];
void dfs(int p) {
    for(auto x: adj[p]) {
        if(visited[x]) continue;
        visited[x]=1;
        if(s[x-1]=='1') {
            cnt++;
            continue;
        }
        dfs(x);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    for(int i=0; i<n-1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) visited[j]=0;
        visited[i]=1;
        if(s[i-1]=='1') dfs(i);
    }
    cout << cnt;
}

 

만점 풀이

제 풀이와 정해가 다를 수 있습니다.

실외에서 시작하는 dfs를 돌립니다. 실외가 실외에 이어져 있다면, 이어져 있는 곳에서 dfs를 다시 돌리고, 만일 실내에 이어져 있다면 cnt값을 1 올립니다. 그리고 반복이 끝날 때 cnt를 vector에 넣습니다.

dfs가 끝나면 처음 시작한 곳에 연결되어있는 모든 실외가 각각 인접한 실내의 개수가 vector에 들어가 있을 것입니다. 이것으로 저희가 dfs를 돌렸던 그 부분그래프의 부분이 실내와 실내 사이의 경로이게 되는 가짓수를 구해봅시다. 

각 실외가 $x_1,\ x_2,\cdots,\ x_t$개의 실내와 인접해 있다고 합시다. 저희가 구해야 하는 값이 무엇인지 예시를 들어 설명해 보겠습니다.

위와 같은 그래프에서 진한 둘레를 가지는 노드가 실외라고 합시다. 그렇다면 $x_1=2,\ x_2=3$이 됩니다. 여기에서 실내와 실내 사이의 경로는 총 20개입니다. 세분화시켜서 보자면 0, 5, 6 사이의 경로 6개, 2, 3 사이의 경로 2개, (0, 5, 6)과 (2, 3)에서 각각 하나씩 골라서 만든 경로가 12개입니다(두 점을 골랐을 때 그 둘을 시작과 끝으로 하는 것은, 한쪽 방향과 반대쪽 방향의 총 2가지가 있습니다).

이렇게 센 것을 바탕으로 일반화를 시켜봅시다. 총 경로의 수를 S라고 하겠습니다. 그렇다면

$$S=\sum_{k=1}^{t} {_{x_k}P_2}+2\sum_{1\leq i <j\leq t}x_i x_j$$

가 됩니다. 위 식을 정리하면

$$S=\sum_{k=1}^{t} (x_k^2-x_k)+2\sum_{1\leq i<j\leq t}x_i x_j$$

로 쓸 수 있습니다. 그러나 이 식의 값을 그대로 구한다면 vector의 원소의 개수에 대해 제곱의 시간복잡도를 가지게 되기 때문에 그닥 효율적인 방법이 되지 못할 것입니다.

그러면 S를 빠르게 구하기 위해 식을 변형시켜서 써봅시다. 윗 식을 변형시키면

$$S=\left (\sum_{k=1}^{t}x_k\right )^2-\sum_{k=1}^{t}x_k$$

로 쓸 수 있습니다. 이렇게 되면 $x_1$부터 $x_t$까지의 합만 구하면 S를 구할 수 있게 되므로 시간을 줄일 수 있습니다.

 

그러나 빼놓은 것이 하나 있습니다. 실내와 실내가 직접 연결되어 있는 경우를 위에서는 구할 수 없게 됩니다. 이 경우는 입력 과정에서 실내끼리 연결되어 있다면 총 경로 수에 2를 더해주는 것으로 구할 수 있습니다.

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans;
bool visited[200001];
string s;
vector<int> adj[200001], v;
void dfs(int p) {
    int cnt=0;
    for(auto x: adj[p]) {
        if(s[x-1]=='0' && !visited[x]) {
            visited[x]=1;
            dfs(x);
        }
        if(s[x-1]=='1') cnt++;
    }
    v.push_back(cnt);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    for(int i=0; i<n-1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        if(s[a-1]=='1' && s[b-1]=='1') ans+=2;
    }
    for(int i=1; i<=n; i++) {
        if(!visited[i] && s[i-1]=='0') {
            long long sum=0;
            v.clear();
            visited[i]=1;
            dfs(i);
            for(int j=0; j<(int)v.size(); j++) sum+=(long long)v[j];
            ans+=sum*sum-sum;
        }
    }
    cout << ans;
}

 

감사합니다.