[BOJ] 24545 Y

 

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

24545번: Y

---

문제

Y-트리는 아래 조건을 만족하는 트리이다.

1.  4개 이상의 정점과 인접한 정점은 없다.
2. 인접한 정점의 개수가 3개인 정점은 정확히 하나만 존재한다.
3. 인접한 정점이 하나뿐인 정점은 정확히 세 개 존재한다.

Y-트리의 크기는 해당 Y-트리를 이루는 정점의 개수와 같다.

 1, 2, … N까지의 번호가 하나씩 매겨진 정점 N개로 이루어진 트리가 주어진다. 주어진 트리에서 정점을 0개 이상 삭제하여 만들 수 있는 가장 큰 Y-트리의 크기를 구하는 프로그램을 작성하시오. 

---

입력

첫째 줄에 트리의 정점 개수를 의미하는 정수 N이 주어진다. (2≤N≤100000)

둘째 줄부터 N−1개 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 u, v가 주어진다. 이는 u번 정점과 v번 정점 사이를 잇는 간선이 존재한다는 의미이다. (1≤u,v≤N, u≠v)

트리를 이루는 모든 간선은 정확히 한 번씩 주어진다.

---

출력

첫째 줄에 주어진 트리에서 만들 수 있는 가장 큰 Y-트리의 크기를 출력한다.

Y-트리를 만들 수 없다면 0을 출력한다.

---

풀이

 

 

왼쪽은 예제 1번의 그래프이고 오른쪽에 파란부분과 빨간부분을 합친 것이 예제의 답이다. 이 문제를 풀 때 핵심은 최대 Y-트리에는 반드시 트리의 지름(파란부분)이 포함 된다는 것이다.

1. 트리 지름의 끝 부분을 찾는다.
2. 트리 지름의 끝 부분을 시작으로 깊이 우선 탐색을 3가지 예외로 나누어서 탐색한다.
   1. 정점에 연결 된 간선이 2개 이상일 경우, 연결 된 간선들로 갈 수 있는 최대 길이를 구하고 가장 긴 길이, 두 번째로 긴 길이, 그리고 시작점부터 해당 정점까지의 길이를 더해 ans보다 크다면 갱신해준다. 최대 길이를 리턴한다.
   2. 정점에 연결 된 간선이 1개 일 경우 연결 된 간선으로 갈 수 있는 길이를 리턴한다.
   3. 정점이 끝 점일 경우 1을 리턴한다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define SWAP(a, b, type) do { \
type temp; \
temp = a;  \
a = b;     \
b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N;
vector<int> v[100001];

bool visit[100001]; // 방문 했는지 안했는지 체크

int start_idx,max_dist=0;

ll ans=0;

void dfs(int start,int dist_sum){// 트리의 지름 중 끝 점을 찾는 탐색
    visit[start]=true;
    bool flag=false;
    int size=v[start].size();
    
    for(int i=0;i<size;i++){
        int go=v[start][i];
        if(!visit[go]){
            dfs(go,dist_sum+1);
            flag=true;
        }
    }
    
    visit[start]=false;
    
    if(flag) return;
    
    if(max_dist<dist_sum){
        start_idx=start;
        max_dist=dist_sum;
    }
}

ll dfs2(int start,ll dist){
    visit[start]=true;
    int size=v[start].size();
    
    if(start!=start_idx) size--; // 트리 지름의 시작점이라면 정점에 연결된 간선의 개수를 줄이면 안된다.
    
    if(size>=2){ // 정점에 연결된 간선의 개수가 2개일 때
        size++;
        vector<ll> tmp;
        for(int i=0;i<size;i++){
            int end=v[start][i];
            if(!visit[end]) tmp.push_back(dfs2(end,dist+1));
        }
        
        sort(tmp.begin(),tmp.end(),greater<int>());
        
        ans=max(ans,tmp[0]+tmp[1]+dist);
        
        return tmp[0]+1; // 두 길이 중 최대 길이를 리턴한다.
        
    }else if(size==1){ // 정점에 연결된 간선의 개수가 1개일 때
        size++;
        for(int i=0;i<size;i++){
            int end=v[start][i];
            if(!visit[end]) return dfs2(end,dist+1)+1;
        }
        
    }
    
    return 1; // 해당 정점이 끝 정점 일 때
}


void input() {
    cin>>N;
    int s,e;
    for(int i=0;i<N-1;i++){
        cin>>s>>e;
        v[s].push_back(e);
        v[e].push_back(s);
    }
}

void init() {}

void solution() {
    dfs(1,0);
    dfs2(start_idx,1);
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}