[c++] codeground 연습문제'우주정거장' (2018년도 SCPC 예선1차)

문제 : www.codeground.org/practice/practiceProblemView

 

우주정거장 문제는, 삼각형을 이루는 모양을 제거할 수 있다는 것이 핵심인듯 보였다.

때문에, 처음 했던 생각은 삼각형의 개수를 세는 것이었다. (이는 틀린 방법이었다.)

 

 

example 1

위와같은 모양이 주어졌다면

 

1. 먼저 입력받은 연결선들의 값들을 모두 순차적으로 정렬한다.

(시간초과를 방지하기 위해, 간선들을 한번씩 탐색하는 동안 모든 검사를 끝내도록 한다.)

 

2. 연결선의 개수만큼 반복문을 돌며, 삼각형이 있는지 찾는다.

3. 1과 3이 연결되어있다면 삼각형이 하나 존재한다는 얘기이기 때문에, 노드 하나를 제거할 수 있다. 

 

4. 총 노드의 개수에서 제거 한 노드를 빼서 답을 구한다. (답:2)

 

같은 방법으로 다음도 생각할 수 있다.

이 경우엔 1과 3이 연결되어있지 않기에 제거할 수 있는 노드가 없고,  지구에서 미리 연결해야될 캡슐의 수는 4이다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200001

using namespace std;

int Answer;
vector<int> store[MAX];                         // 기본 연결 내용들을 저장한다.

int main(int argc, char** argv)
{
    int T, test_case;

    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {
        Answer = 0;
        int n, m, first_element = 1,count=0;
        vector <pair<int,int>> v;                // 정렬된 값을 위해
        vector<int> link_list;                   // 현재 노드와 연결된 값들을 저장
        
        for(int i=0 ; i< MAX ; i++){             // O(n):200001
            store[i].clear();
        }
        
        scanf("%d %d",&n,&m);
        
        // 입력 시 정렬을 위해 (작은값 , 큰값) 으로 1차 정렬하여 입력해준다.
        for(int i=0 ; i< m ; i++){               // O(m):400001
            int node1,node2;
            scanf("%d %d",&node1, &node2);
            
            if(node1 > node2){
                store[node2].push_back(node1);
                v.push_back(make_pair(node2,node1));
            }
            else{
                store[node1].push_back(node2);
                v.push_back(make_pair(node1,node2));
            }
        }
        
        // 정렬
        sort(v.begin(), v.end());                 // O(mlogm)
        
        
        for(int i=0 ; i< m ; i++){                // O(m):400001
            if(v[i].first == first_element){      // 현재 노드와 연결된 노드들 저장
                link_list.push_back(v[i].second);
            }
            
            else{
            
                // 애조체 삼각형을 이룰 수 없으면 다음 단계로 넘어간다.
                if(link_list.size()==1 || link_list.size() ==0){
                    link_list.clear();
                    first_element++;
                    link_list.push_back(v[i].second);
                }
                
                // 삼각형을 이루고있는지 확인한다.
                else{
                    for(int j=0; j< link_list.size() ; j++){
                        for(int k=0 ; k< store[link_list[j]].size() ; k++){
                            vector<int>::iterator iter;
                            iter = find(store[first_element].begin(),
                                   store[first_element].end(),store[link_list[j]][k]);
                            if(iter != store[first_element].end())
                                count++;
                        }
                    }
                    link_list.clear();
                    first_element++;
                    link_list.push_back(v[i].second);
                }
            }
            
            // 마지막 값이 link_list에 들어가기만 하고 끝날 가능성이 있기 때문에.
            if(i == m-1){
                for(int j=0; j< link_list.size() ; j++){
                    for(int k=0 ; k< store[link_list[j]].size() ; k++){
                        vector<int>::iterator iter;
                        iter = find(store[first_element].begin(),
                               store[first_element].end(),store[link_list[j]][k]);
                        if(iter != store[first_element].end())
                            count++;
                    }
                }
            }
        }
        
        Answer = n-count;
        cout << "Case #" << test_case+1 << endl;
        cout << Answer << endl;
    }

    return 0;
}

 

하지만 이는 다음과 같은 예외가 있었다.

1-4-5 , 3-4-5 삼각형 두개가 있기 때문에, 실제 답은 5가 되어야 되지만 삼각형 2를 제외한 3이 답으로 출력되었다.

때문에 다른 방법을 생각했다.

 

 

 

 

 

 

 

 

두번째 방법으론, 간선이 두개인 노드들을 모두 큐에넣고, 하나씩 꺼내며 삼각형인지 확인하였다.

 

첫번쨰 방법은 삼각형의 수를 단순히 찾는 것이었지만, 두번째는 완성된 모양에서, 조건에 맞는 노드를 찾아 제거해가며 답을 찾았다.

 

위 그림과 같은 경우 파란색 노드가 1,3번에 연결되어있기에 4는 큐에 들어 갈 것이고, 이때 1,3이 연결되어있다면 4는 제거할 수 있게된다.

연결되어있지 않다면 4는 제거하지 않고 다음으로 넘어간다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 200001

using namespace std;

int Answer;
int cnt;
vector<int> store[MAX];
queue<int> q;

// 노드를 제거해준다.
// 노드를 제거함의 의미는 해당 노드와 연결된 간선을 지워주면 된다.
// 제거 할 노드와 연결되어있던 노드들의 간선 수를 확인하여 간선의 수가 2라면 큐에 넣어준다.(제거 후보)
void remove_node(int current_node){
    int node1 = store[current_node][0];
    int node2 = store[current_node][1];
    store[current_node].clear();
    store[node1].erase(remove(store[node1].begin(),store[node1].end(),current_node),store[node1].end());
    store[node2].erase(remove(store[node2].begin(),store[node2].end(),current_node),store[node2].end());
    
    if(store[node1].size() == 2)
        q.push(node1);
    if(store[node2].size() == 2)
        q.push(node2);
    
}

// 해당 노드가 삼각형으로 이루어져있다면 해당 노드를 제거해준다.
void check_triangle(int current_node){
   
    int node1 = store[current_node][0];
    int node2 = store[current_node][1];
    for(int i=0 ; i< store[node1].size() ; i++){
        if(store[node1][i] == node2){
            cnt++;
            remove_node(current_node);
            return;
        }
    }
}




int main(int argc, char** argv)
{
    int T, test_case;

    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {
        Answer = 0;
        cnt = 0;
        int n, m;
        queue<int> empty;
        
        for(int i= 0 ; i< MAX ; i++){    // O(n):200000
            store[i].clear();
        }
        swap(q,empty);
        
        scanf("%d %d",&n,&m);
        
        for(int i= 0 ; i< m ; i++){      // O(n):400000
            int node1,node2;
            scanf("%d %d",&node1,&node2);
            store[node1].push_back(node2);
            store[node2].push_back(node1);
        }
        
        // 2개의 간선을 가지고있는 노드들을 큐에 넣어준다.
        for(int i=1 ; i<= n ; i++){      // O(n):200000
            if(store[i].size() == 2){
                q.push(i);
            }
        }
        
        // 큐가 비워질 때 까지 제거 가능한 노드인지 확인한다.
        while(!q.empty()){
            int current_node = q.front();
            q.pop();
            check_triangle(current_node);
        }
        
        Answer = n - cnt;
        cout << "Case #" << test_case+1 << endl;
        cout << Answer << endl;
    }

    return 0;
}