백준 - 1762. 평면그래프와 삼각형

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

 

평면그래프가 노드간의 연결 정보를 통해 주어질때 그래프상의 삼각형을 모두 다 찾는 문제이다.

점의 갯수가 10만개 이기에 완전탐색은 불가능하며 메모리 또한 신경써서 다뤄줘야 한다.

 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<vector<int>> nodes;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, M;
 
    cin >> N >> M;
    nodes.assign(N, vector<int>());
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        a--, b--;
        nodes[a].push_back(b);
        nodes[b].push_back(a);
    }
    
    for (int i = 0; i < N; i++)
        sort(nodes[i].begin(), nodes[i].end());
    
    int ret = 0;
    int c;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < nodes[i].size(); j++) {
            a = i;                //a번 노드
            b = nodes[i][j];    //a번 노드와 연결된 j번째 노드의 번호
            if (b < a)
                continue;
 
            if (nodes[a].size() > nodes[b].size()) swap(a, b);
 
            //a, b번 점과 동시에 연결된 점을 찾는다.
            for (int k = 0; k < nodes[a].size(); k++) {
                c = nodes[a][k];
                // c는 a와 연결된 k번째 점의 번호이다.
                // c가 b와도 연결 되어 있는지 판단한다.
 
                bool chk = binary_search(nodes[b].begin(), nodes[b].end(), c);
                if (chk == true) {
                    ret++;
                }
 
            }
        }
    }
 
    cout << ret / 3 << endl;
 
    return 0;
}

점 하나를 선택한 후에 해당 점과 연결 되어 있는 점을 하나 더 선택한다. 그리고 2개의 점과 동시에 연결되어 있는 점을 이진탐색으로 찾는 방식으로 풀었다.

 

7번째 줄의 nodes는 특정 점과 연결된 점의 번호들을 저장한다.

가령 nodes[a][b] 는 a번 점과 연결된 b번째 점의 번호이다.

입력이 끝나고 nodes에 점들이 채워젔으면 26번째 줄에서 후에 이진탐색을 하기위해 정렬한다.

 

31번째 줄에서 임의의 점을 순차적으로 하나씩 선택하고

32번재 줄에서 앞서 선택한 점과 연결된 점을 하나 더 선택한다.

a,b 점을 조사하는것과 b,a 점을 조사하는 것은 같으므로 중복된 탐색을 지우기 위해 대소관계를 이용한다

 

a,b와 동시에 연결된 점의 갯수를 알아야 하므로 a와 연결된 점들을 선형탐색하며 해당점이 b에도 연결되어 있는지 이진탐색한다.

선형탐색보다 이진탐색이 더 빠르므로 둘중에 길이가 더 긴쪽을 이진탐색, 짧은쪽을 선형탐색 하도록 하기 위해 길이를 비교하여 크기가 작은쪽이 a, 큰쪽이 b가 되도록 swap 해준다.

그리고 a,b에 동시에 존재하는 점을 찾고 있다면 갯수를 더해준다.

 

위와같은 방법으로는 하나의 삼각형에 대해 3가지 경우의 수가 나오므로(0-1-2, 1-2-0, 2-1-0) 3을 나눠서 출력하게끔 한다. 점의 갯수가 너무 많으므로 중복을 사전에 차단할 방법은 이진탐색을 빼면 떠오르지 않고 성능도 안좋을듯하다.

 

 

아직 위 문제의 시간 복잡도가 정확히 어떻게 되는지 잘 모르겠다. 수학 공부를 지속적으로 해줘야겠다.

42번재 줄에서 nodes[a][k] 대신에 nodes[i][k] 를 넣어서 틀린 부분을 한참동안 해맸다.