(SWEA c++)6057. 그래프의 삼각형

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbHcWd6AFcDFAV0&categoryId=AWbHcWd6AFcDFAV0&categoryType=CODE

SW Expert Academy

그래프에서 3개의 간선이 서로 이어져있는지 확인하면 된다.

 

x, y 좌표를 입력받아 해당 좌표의 map을 true로 바꾼다.

3중 for문을 통해 [i][j], [j][k], [k][i]가 true이면 ans++을 해주고,

마지막에는 6을 나눠 출력한다.

왜냐하면 [i][j], [j][i] / [j][k], [k][j] / [k][i], [i][k] 의 경우를 살피기 때문이다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int x, y, N, M;
        int ans = 0;

        cin >> N >> M;
        
		vector<vector<bool>> v(51, vector<bool>(N + 1, false));
        
        for(int i = 0; i < M; i++)
        {
            cin >> x >> y;
            v[x][y] = true;
            v[y][x] = true;
        }
        
        for(int i = 1; i <= N; i++)
        {   
            for(int j = 1; j <= N; j++)
            {
                for(int k = 1; k <= N; k++)
                {
                    if(v[i][j] && v[j][k] && v[k][i])
                        ans++;
                }
            }
        }
        
        cout << "#" << tc << " " << ans / 6 << endl;
    }
    return 0;
}