6057. 그래프의 삼각형(D3)

문제 링크  https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbHcWd6AFcDFAV0&categoryId=AWbHcWd6AFcDFAV0&categoryType=CODE

그래프에서 삼각형 즉, 3개의 노드가 서로간의 간선이 존재하여 싸이클을 이루는 경우를 찾는 문제다. 감사하게도 N의 최대값이 50이므로 O(N^3)이 된다고 해도 시간초과가 발생하지 않는다.
※ M의 최대값은 N(N-1)/2이므로 시간초과가 발생할 가능성이 매우 높다 !

가장 먼저 [N][N] 크기의 배열을 먼저 생성했다. 그리고 들어오는 간선들을 a와 b 사이에 간선이 있다고 할 때 [a][b], [b][a] 배열의 값을 1로 만들어주는 것으로 기본 세팅을 끝냈다.

다음으로 각 노드마다 간선이 있는 노드들의 번호를 새로운 일차원 배열 temparr에 저장한다. temparr을 앞에서부터 탐색하며 모든 노드간에 서로 간선이 있는 경우의 개수를 Count 해준다.
이 때, 싸이클에 포함되는 노드가 3개, 간선의 방향에 따라 2개( 정방향, 역방향 )이 모두 Count 된다.
즉, 중복을 제거해주기 위해 6 (3 [ 싸이클에 포함되는 노드개수 ] * 2 [ 간선이 중복 Count 되는 횟수 ])으로 나눠주면 쉽게 정답을 찾을 수 있다.

이 문제에서 최악의 경우는 노드가 50개 존재하며 모든 노드 간에 간선이 존재하는 경우이다. 이 경우가 50 * 50 * 50 = 125,000 이므로 시간초과를 피할 수 있다.

- 소스코드 -

#include<iostream>
 
using namespace std;
 
int main(void) {
    int T;
    cin >> T;
    
    for (int test_case = 1; test_case <= T; test_case++) {
        int result = 0;
        int N, M;
        scanf("%d", &N);
        scanf("%d", &M);
        
        int graph[50][50] = { 0 };
        
        for (int i = 0; i < M; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            graph[a - 1][b - 1]++;
            graph[b - 1][a - 1]++;
        }
 
        for (int i = 0; i < N; i++) {
            int temparr[50] = { 0 };
            int index = 0;
            for (int j = 0; j < N; j++) {
                if (graph[i][j]) {
                    temparr[index] = j;
                    index++;
                }
            }
            for (int j = 0; j < index; j++) {
                for (int k = 0; k < index; k++) {
                    if (graph[temparr[j]][temparr[k]]) {
                        result++;
                    }
                }
            }
        }
        result /= 6;
 
        printf("#%d %d\n", test_case, result);
    }
}