[python] SWEA - 6057. 그래프의 삼각형

🤔문제 해결

• D3 | 그래프

💨 문제 그대로 i 와 j 와 k 가 연결된 ( 삼각형 ) 갯수를 찾는것

💨 문제에서 i < j < k 가 왜 있는지는 모르겠지만 3 중 for 문으로 i, j ,k 를 골라서 서로가 연결되어 있는지 확인

 

💻소스 코드

from _collections import defaultdict

for tc in range(int(input())):
    N, M = map(int, input().split())

    adj = defaultdict(set)
    for _ in range(M):
        s, e = map(int, input().split())
        adj[s].add(e)
        adj[e].add(s)

    total = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            for k in range(j + 1, N + 1):
                if i in adj[j] and j in adj[k] and k in adj[i]:
                    total += 1

    print(f'#{tc + 1} {total}')
 

📕문제 확인

출처: SW Expert Academy

SW Expert Academy