1. 잔디밭과 개미굴

문제 링크

Codeup: 5313

잔디밭의 개미굴

Baekjoon: 28328

28328번: 잔디밭의 개미굴

 

문제 선정 과정

먼저 문제가 굉장히 길었다.

대략적으로 요약하면 다음과 같다.

• 트리 구조의 그래프가 주어지고, 각 노드는 0 또는 1의 데이터를 담는다.
• 임의의 간선을 선택했을 때, 해당 간선이 잇는 두 노드의 데이터가 모두 1이면 안 된다.
• 처음 그래프에서 모든 노드의 데이터의 합의 최댓값을 N이라 하자.
• 이때 임의의 서로 다른 두 정점을 골라 이를 연결했을 때,
  여전히 모든 노드의 데이터의 합의 최댓값이 N이 되는 경우의 수를 구하여라.

트리 탐색 문제임을 알 수 있었고, 많은 상황을 효율적으로 관리하여 경우의 수를 구한다는 점에서

동적 계획법을 사용하는 문제일 것이라 예상했다.

이전부터 동적 계획법을 사용하는 문제들을 많이 풀어보며 연습해왔기 때문에 한번 풀어보겠다고 생각했다.

 

 

문제 풀이 전략

탐색기반 설계와 관계기반 설계를 사용하여 해결하였다.

 

먼저 탐색기반 설계는 문제에서 주어진 데이터들을 특성에 맞게 구조화하고 이를 적절하게 탐색하여

원하는 해를 만드는 방법을 의미한다.

 

탐색하는 자료구조에는 크게 선형과 비선형으로 나뉘는데,

선형구조는 배열이나 연결리스트로 표현할 수 있는 구조이고,

비선형구조는 트리나 그래프로 표현되는 구조를 일컫는다.

 

다음으로 관계기반 설계는 해를 구하는 행위를 하나의 함수로 표현한 후 이 함수들의 관계를 이용해서 해를 구하는 설계 방법이다.

보통 문제의 정의 및 상태를 하나의 함수로 표현 후, 함수들과의 관계를 점화식 등을 이용하여 나타낸다.

 

대표적으로 Dynamic Programming이라는 기법이 있다.

현재 상태를 탐색하여 저장한 후, 다음에 관계식을 통해 이 값이 요구되면 저장된 값을 바로 내놓는 방법이다.

 

해당 문제에서는 트리 그래프를 탐색하고 서브트리에 대한 관계기반 설계를 활용하여 문제를 해결하였다.

 

 

최댓값을 만드는 경우가 유일할 때
이는 바꿔 말하면, 임의의 데이터가 1인 노드에 대해 인접한 노드와 데이터를 바꾼다면
반드시 어떠한 간선에 의해서 다른 데이터가 1인 노드와 연결됨을 의미한다.

즉, 이러한 상태에서 만약 데이터가 1인 서로 다른 두 노드를 연결한다면,
더 이상 최댓값을 유지하며 데이터를 관리할 수 없게 된다.

두 데이터 중 하나만 이동한다면 다른 데이터 1의 노드와 연결되고,
두 데이터 모두 이동하여 방법이 나왔다면, 추가했던 간선을 제거해도 문제가 없으므로
최댓값을 만드는 경우가 유일하다는 가정에 모순이 발생한다.

한편, 두 노드를 연결했을 때 두 노드의 데이터가 모두 1이라면 아무 문제 없다.

따라서 노드의 개수를 $N$, 데이터의 총 합을 $P$라 하면
답은 $\frac{N(N-1)}{2} - \frac{P(P-1)}{2}$ 가 된다.

 

 

최댓값을 만드는 방법이 여러 가지일 때
다음과 같은 경우를 생각할 수 있다.

이때 가능한 방법은 다음 두 가지이다.

최댓값을 만드는 방법이 유일할 때는 그 방법을 기준으로 두 노드 모두 1이라면 항상 불가능했다.
그러나, 최댓값을 만드는 방법이 여러 개라면, 두 노드를 연결했을 때
둘 다 1이 되지 않게 하는 방법이 하나라도 존재한다면 그 방법으로 다시 배치할 수 있게 된다.

따라서 이 경우에는 모든 방법에서 공통적으로 1인 노드들을 연결하지만 않는다면
마찬가지로 성립하는 방법이 된다. 

 

시행착오

사실 이렇게 문제를 어떻게 해결할 지 생각하는 것은 그렇게 어렵지 않았으나,

이를 구현하는 방법을 떠올리는 것이 굉장히 어려웠다.

 

먼저 최댓값을 구하는 과정 자체는 트리 DP를 활용하여 손쉽게 구할 수 있다.

그러나 방법이 여러 개일 때, DP로 방법을 직접 저장하기는 꽤나 난감하다.

따라서 방법을 직접 구하지 않고, 꼭 1이 되어야만 하는 노드들을 세야 한다고 생각했다.

 

풀이 과정

먼저 최댓값을 트리 DP를 활용하여 구하는 과정이다.

현재 노드가 1이라면 서브트리들의 루트 노드가 0일 때 최댓값을 구해주면 되고,

현재 노드가 0이라면 모든 서브트리들의 경우의 최댓값을 다 더해주면 된다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n;
vector<int> node[250001];

int dp[250001][2];

int DP(int cur, int c, int parent)
{
  int &res = dp[cur][c];
  if(res != -1) return res;

  res = c;
  for(auto nxt: node[cur])
    {
      if(parent == nxt) continue;

      if(c == 1) res += DP(nxt, 0, cur);
      else res += max( DP(nxt, 0, cur) , DP(nxt, 1, cur)) ;
    }

  return res;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  for(int i=1;i<n;i++)
    {
      int p,q;
      cin >> p >> q;
      node[p].push_back(q);
      node[q].push_back(p);
    }
  memset(dp,-1,sizeof(dp));

  DP(1,0,-1);
  DP(1,1,-1);
}

 

이제 필수적으로 1을 저장해야만 하는 노드들을 찾아야 한다.

여기서 사용한 아이디어는 다음과 같다.

• 서브트리의 루트 노드가 0인 경우와 1인 경우 모두 최댓값이 나온다면,
  그 서브트리의 루트 노드는 필수적으로 저장하지 않아도 된다.

따라서 탐색으로 만들어 놓은 DP 테이블을 참조하며, 재귀적으로 트리를 탐색하면 된다.

아래는 탐색 함수이다. a는 처음에 모두 1로 채워져 있다.

void track(int cur, int c, int parent)
{
  a[cur] &= c;

  for(auto nxt: node[cur])
    {
      if(nxt == parent) continue;

      if(c == 1) track(nxt, 0, cur);
      else
      {
        if(DP(nxt, 0, cur) >= DP(nxt, 1, cur)) track(nxt, 0, cur);
        if(DP(nxt, 0, cur) <= DP(nxt, 1, cur)) track(nxt, 1, cur);
      }
    }
}

 

이렇게 하면 모든 경우에 대해 탐색을 할 수 있고,

a에 남은 1은 해당 인덱스의 노드에는 반드시 1이 담겨야 한다는 것을 의미한다. (모든 탐색에서 1이였으므로)

따라서 a의 값들을 더해주면 필수적으로 1이 되어야만 하는 노드의 수를 구할 수 있다.

이를 이용하여 계산해주면 된다.

 

그러나 위의 코드대로 구성해주니 시간초과가 났다.

한 번 탐색한 경우를 다시 탐색해주지 않게 하기 위해, visited 배열을 선언하여 기록해주었다.

그 결과 문제를 해결할 수 있었다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
typedef long long int LL;

LL n;
vector<int> node[250001];

int dp[250001][2];
int a[250001];

bool visited[250001][2];

int DP(int cur, int c, int parent)
{
  int &res = dp[cur][c];
  if(res != -1) return res;

  res = c;
  for(auto nxt: node[cur])
    {
      if(parent == nxt) continue;

      if(c == 1) res += DP(nxt, 0, cur);
      else res += max( DP(nxt, 0, cur) , DP(nxt, 1, cur)) ;
    }

  return res;
}

void track(int cur, int c, int parent)
{
  if(visited[cur][c]) return;
  visited[cur][c] = true;
  
  a[cur] &= c;

  for(auto nxt: node[cur])
    {
      if(nxt == parent) continue;

      if(c == 1) track(nxt, 0, cur);
      else
      {
        if(DP(nxt, 0, cur) >= DP(nxt, 1, cur)) track(nxt, 0, cur);
        if(DP(nxt, 0, cur) <= DP(nxt, 1, cur)) track(nxt, 1, cur);
      }
    }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  for(int i=1;i<n;i++)
    {
      int p,q;
      cin >> p >> q;
      node[p].push_back(q);
      node[q].push_back(p);

      a[i] = 1;
    } a[n] = 1;
  
  memset(dp,-1,sizeof(dp));

  if(DP(1,0,-1) >= DP(1,1,-1)) track(1,0,-1);
  if(DP(1,0,-1) <= DP(1,1,-1)) track(1,1,-1);

  LL p = 0;
  for(int i=1;i<=n;i++) p += a[i];

  cout << n*(n-1)/2 - p*(p-1)/2;
}

 

 

느낀 점

정보올림피아드 문제라길래 이걸 풀 수 있을까 고민도 되었지만,
조금씩 문제를 해결하면서 문제를 해결했다는 것이 뿌듯했다.

 

또한 그동안의 DP 문제와 달리 얻은 DP 테이블을 활용하여 그래프 탐색을 진행한다는 게 굉장히 인상 깊었다.