아침 산책 21606

문제

접근 방법

각 실내에서 닿을 수 있는 다른 실내의 경우를 모두 세어주는 방법도 있지만 그렇게 하면 너무 많은 경우를 확인해야 한다.
직접 트리를 그려서 각 경우의 개수를 확인해 보면 (실내의 개수)*(실내의 개수-1)의 값이 나온다. (2개-2, 3개-6, 4개-12...)

즉 실내의 개수만 알게 된다면 해당 구역은 계산으로 해결해 줄 수 있다는 것이다.
계산으로 해결해 나가며 탐색하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
typedef unsigned long long ull;
int N;
ull ret = 0;
string A;
vector<vector<int>> graph;
vector<bool> visted;
ull bfs(int i)
{
    ull cnt = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int next : graph[cur])
        {
            if (A[next - 1] == '0')
            {
                if (visted[next])
                    continue;
                visted[next] = true;
                q.push(next);
            }
            else
            {
                ++cnt;
            }
        }
    }
    return cnt;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> A;
    graph = vector<vector<int>>(N + 1, vector<int>());
    visted = vector<bool>(N + 1);
    for (int i = 1, u, v; i < N; ++i)
    {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        if (A[u - 1] == '1' && A[v - 1] == '1')
            ret += 2;
    }
    for (int i = 1; i <= N; ++i)
    {
        if (visted[i] || A[i - 1] == '1')
            continue;
        visted[i] = true;
        ull cnt = bfs(i);
        ret += cnt * (cnt - 1);
    }
    cout << ret;
    return 0;
}

풀이

조합으로 계산하는 방법까진 도달했다.
실내에서 탐색을 시작하여 뻗어나가는 식이었는데 그렇게 하자 48점까지 밖에 도달 못 했다.

찾아보니 실외에서 탐색을 시작하는 것이 더 효율적이었다. (실내에서 시작할 시 방문 처리를 해결하기 까다롭다)
실내 사이에 실외가 없는 경우에 입력에서 2를 더하면 된다는 것도 다른 사람의 풀이를 통해 알게 됐다. (실외에서 출발하면 실내 사이에 출발할 공간이 없다)