백준 4305번: 성격 진단 테스트 (C++)

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

4305번: 성격 진단 테스트

---

Solved By: SCC (Tarjan Algorithm)

 

문제에서 말하는 모순이라는 건 선택한 어떤 활동들이 같은 SCC 안에 있는지 묻는 것입니다.

문자형 변수들을 숫자로 바꾸어서 SCC를 구해주고, SCC끼리 정렬하여 출력하면 풀리는 문제였습니다.

 

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define MAX 27
using namespace std;

vector<int> adj[MAX];
vector<vector<int>> SCC;
stack<int> s;
int visitedOrder[MAX];
bool isSCC[MAX];
bool exist[MAX];
int order;

bool cmp(vector<int> a, vector<int> b){
    return a[0] < b[0];
}

int dfs(int now){
    int minOrder = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){
            minOrder = min(minOrder, dfs(next));
        }
        else if(!isSCC[next]){
            minOrder = min(minOrder, visitedOrder[next]);
        }
    }
    
    if(visitedOrder[now] == minOrder){
        vector<int> scc;
        while(1){
            int temp = s.top(); s.pop();
            scc.push_back(temp);
            isSCC[temp] = true;
            if(temp == now) break;
        }
        
        SCC.push_back(scc);
    }
    
    return minOrder;
}

void tarjan(){
    fill(visitedOrder, visitedOrder + MAX, -1);
    fill(isSCC, isSCC + MAX, false);
    for(int i = 1; i <= 26; i++){
        if(exist[i]){
            if(visitedOrder[i] == -1) dfs(i);
        }
    }
}

int n;
int main(){
    while(true){
        cin >> n;
        if(n == 0) break;
        
        SCC.clear();
        fill(exist, exist + MAX, false);
        for(int i = 0; i < MAX; i++) adj[i].clear();
        while(!s.empty()) s.pop();
        order = 0;
        
        for(int i = 0; i < n; i++){
            vector<int> tmp;
            for(int j = 0; j < 5; j++){
                char c; cin >> c;
                tmp.push_back(c - 'A' + 1);
                exist[c - 'A' + 1] = true;;
            }
            char c2; cin >> c2;
            int v = c2 -'A' + 1;
            for(int j = 0; j < tmp.size(); j++){
                if(tmp[j] == v) continue;
                adj[v].push_back(tmp[j]);
            }
        }
        
        tarjan();
        
        for(int i = 0; i < SCC.size(); i++){
            sort(SCC[i].begin(), SCC[i].end());
        }
        sort(SCC.begin(), SCC.end(), cmp);
        
        for(int i = 0; i < SCC.size(); i++){
            for(int j = 0; j < SCC[i].size(); j++){
                cout << (char)((SCC[i][j] - 1) + 'A') << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
}