SWEA 6057 그래프의 삼각형(with Python)

내가 생각하는 Solution

• 난 다른 사람에 비해서 너무 어렵게 접근해서 풀었다...

• 문제를 조금 더 쉽게 생각하는 힘을 길러야할 듯...

문제에서 생각해볼 점

1. 노드(node)를 하나씩 순회합니다.

2. 해당 노드와 연결된 노드(neighbor)를 순회합니다.

3. neighbor와 연결된 노드(n_neighbor)를 순회하면서 n_neighbor가 node에 포함되는지 확인합니다. (count 하기)

4. 이렇게하면 테스트 케이스 기준으로 ([1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]) 로 하나의 삼각형에 대해서 총 6개가 카운트 됩니다. -> 따라서 마지막에 6으로 나누어 출력합니다.

코드 구현

T = int(input())
 
for tc in range(1, T+1):
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
 
    for i in range(M):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)
 
    cnt = 0
    for node in range(1, N+1):
        for neighbor in adj[node]:
            for n_neighbor in adj[neighbor]:
                if n_neighbor in adj[node]:
                    cnt += 1
    print(f'#{tc} {cnt//6}')