[백준] 14380 : BFFS$($Large$)$

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

문제 분석

 각 학생별로 친한 친구(BFF)가 있을 때, 모든 학생이 BFF와 인접하게끔 가장 큰 원을 이루는 방식을 묻는 문제이다. 이때, 조건을 만족하면서 원을 구성하는 방식은 2가지이다. 1번째는 전체 노드가 하나의 사이클을 이루는 방식이고 2번째는 2개의 체인이 끝부분에서 서로를 참조해 이어진 형태이다.

(화살표는 해당 노드의 BFF를 가르킨다.)
1. 전체 노드가 사이클을 이룬다.
ex) $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow (1)$
2. 두 가지 선형으로 이루어진 체인의 끝부분이 서로를 참조해 결합해 있다.
ex) $1 \rightarrow 2 \rightarrow 3 \leftrightarrow 4 \rightarrow 5$
ex) $(1 \rightarrow 2\leftrightarrow 3 \rightarrow 4) (5 \rightarrow 6\leftrightarrow 7 \rightarrow 8)$

 1번째 케이스의 경우, 스택을 통한 DFS로 사이클을 확인가능하다. 방문 여부를 마킹하면서 노드를 스택에 쌓아가며 이미방문한 노드가 나올시에는 이미 방문한 노드가 나올때까지 스택을 위부터 팝시키며 사이클의 길이를  특정하면 된다.
 2번째 케이스의 경우, 우선 2가지 노드로만 이루어진 사이클을(결합부) 바탕으로 2노드에서 가장 긴 테일의 크기를 가지는 체인을 선택하면 된다.

문제 해결 전략

 전체 알고리즘은 대략적으로 다음과 같다. 자세한 내용은 코드상에 있다. 

코드

#include <iostream>
#include <vector>
#include <stack>
#include <tuple>

using namespace std;

//문제분석
// T<=100, N<=1000
// 각 학생의 BFF가 인접한 상태로 가장 큰 원을 만드는 문제 
// 원을 만드는 케이스는 크게 2가지이다,
// 1. 노드 자체가 순환, 2개 순환이 아닌 이상 결합불가  
// (1 -> 2 -> 3 -> 4 ->(1))
// 2. 두 선형 노드의 결합 (기본적으로 결합부를 기준으로 가장 긴 꼬리)
// (1 -> 2 -> 3 <-> 4 <- 5 <- 6)
// 1번 케이스는 스택을 사용하여 N의 복잡도로 처리가능하다.
// 노드를 쌓는 중 이미 방문한 노드가 나오면 그 노드가 나올때까지 pop하고 pop한 개수를 추척
// 동시에 2번케이스의 결합부가 되는 2노드 만으로 사이클을 이룬 케이스도 탐색
// 각 결합 노드의 가장 긴 꼬리도 이과정에서 동시에 탐색 
//=====================================================================
//해결전략
// 1. 노드를 방문하여 visited를 true로 바꾼다.
// 2. 노드가 done한 노드인지 확인한다.
// 2-1. 완료된 노드라면 해당 노드의 깊이를 체크한다.
// 2-2. 스택을 순서대로 팝하면서 깊이를 1씩 증가 시키며 done을 true로 바꾼다,
// 3. 노드가 visited한 노드인지 확인한다.
// 3-1. 이미 visited한 노드일시 해당 노드가 나올때까지 스택을 팝하면서 길이를 체크한다. (done check)
// 3-2. 길이가 2일시 따로 표기한다.
// 3-3. 스택을 순서대로 팝하면서 깊이를 1씩 증가 시키며 done을 true로 바꾼다,
// 4. visited도 done도 아닌 노드일시 1번 부터 반복한다.
// 5. 아직 처리하지않은 임의의 노드에대해 1번 부터 수행한다.
//=====================================================================
//필요자료형
//변수
// vector<int> bff : bff 저장용
// stack<int> stack : 전체 알고리즘에 쓰이는 stack
// vector<bool> done , visited : 전체 알고리즘에 쓰이는 마스킹
// vector<pair<int,int>> depth : 깊이를 위한 일종의 dp (root, depth)의 형태 사이클 구성원수는 (self,0)인 값
// vector<pair<int,int>> cycleByTwo : 두 개 사이클 따로 저장용
// vector<int> longestTail : depth를 기반으로 루트별 가장 긴 테일만 저장
// int longestCycle : 가장 긴 사이클
// int longestChain : 가장 긴 2번 케이스
//함수
// 바로 구현

int T;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    cin >> T;
    vector<int> answers;
    for (int t = 0; t < T; t++)
    {
        int N;
        cin >> N;

        stack<int> studentStack;
        vector<bool> done(N,false) , visited(N,false);
        vector<pair<int,int>> depth(N,make_pair(-1,-1));
        vector<pair<int,int>> cycleByTwo;
        vector<int> bffs;

        int longestCycle(0),longestChain(0);

        for (int i(0),temp(0); i < N; i++){
            cin >> temp;
            bffs.push_back(temp-1);
        } 

        for (int i = 0; i < N; i++)
        {
            if (done[i]) continue;
            int curStudent=i;
            while(1){
                if (done[curStudent]){
                    int rootStudent, curDepth;
                    tie(rootStudent,curDepth)=depth[curStudent];
                    while(!studentStack.empty()){
                        curStudent=studentStack.top();
                        depth[curStudent]=make_pair(rootStudent,++curDepth);
                        done[curStudent]=true;
                        studentStack.pop();
                    }
                    break;
                }
                if (visited[curStudent]){
                    int cycleStart(curStudent), cycleSize(0);
                    while(1){
                        curStudent=studentStack.top();
                        depth[curStudent]=make_pair(curStudent,0);
                        done[curStudent]=true;
                        studentStack.pop();
                        cycleSize++;
                        if (curStudent==cycleStart){
                            if (cycleSize==2) cycleByTwo.push_back(make_pair(cycleStart,bffs[cycleStart]));
                            break;
                        } 
                    }
                    longestCycle=max(longestCycle,cycleSize);

                    int rootStudent, curDepth;
                    tie(rootStudent,curDepth)=depth[curStudent];
                    while(!studentStack.empty()){
                        curStudent=studentStack.top();
                        depth[curStudent]=make_pair(rootStudent,++curDepth);
                        done[curStudent]=true;
                        studentStack.pop();
                    }
                    break;
                }

                studentStack.push(curStudent);
                visited[curStudent]=true;
                curStudent=bffs[curStudent];
            }
        }

        vector<int> longestTail(N,0);
        for(auto d:depth) longestTail[d.first]=max(d.second,longestTail[d.first]);
        for(auto _pair:cycleByTwo) longestChain+=2+longestTail[_pair.first]+longestTail[_pair.second];

        answers.push_back(max(longestCycle,longestChain));
    }

    for (size_t i = 0; i < T; i++) cout << "Case #" << i+1 << ": " << answers[i] << "\n";
}