[파이썬 삼성sw] 6057 그래프의 삼각형

[파이썬 삼성sw] 6057 그래프의 삼각형

문제

정점이 N개, 간선이 M개 있는 그래프가 주어진다. 정점에는 1번에서 N번까지의 번호가 붙어 있다.

이때 i 번 정점과 j 번 정점 사이에, j번 정점과 k번 정점 사이에, k번 정점과 i번 정점 사이에 모든 간선이 있는

(i, j, k)를 삼각형이라고 하자 (i <j <k)

이때 삼각형 개수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두정수 N, M이 공백으로 구분되어 주어진다.

다음 M개의 줄에는 두 정수 X, Y가 주어진다.

이는 X번 정점과 Y번 정점 사이에 간선이 있다는 의미이다.

출력

삼각형의 개수를 출력한다.

풀이

나는 DFS를 이용하여 풀었다.

1번 정점에서부터 시작해서 1번 정점에서 연결된 모든 정점 DFS 방식으로 탐색하여 3개의 정점을 거쳐가서 다시 자기 자신으로 돌아온다면 삼각형 하나가 완성된다.

이때 조건은 i <j <k 이기에 DFS로 탐색할 때 다음 정점은 그전의 정점보다 크다는 조건을 추가해야 한다.

코드

def dfs(start,count,v):
    global ans
    if count==3:
        if start in g[v]:
            ans+=1    
        return
    for i in g[v]:
        if i>v:
            dfs(start,count+1,i)


test=int(input())

for t in range(1,test+1):
    ans=0
    n,m=map(int,input().split())
    g=[[] for _ in range(n+1)]
    for _ in range(m):
        x,y=map(int,input().split())
        g[x].append(y)
        g[y].append(x)
    for i in range(1,n+1):  
        dfs(i,1,i)
    print(f"#{t} {ans}")

DFS 코드에서 start는 정점의 시작위치, count는 몇 개의 정점을 지나왔는지 확인하고 , v 현재 추가되는 정점을 의미한다.

이때 count=3이면 삼각형이 이루어지는 조건을 만족하는 거기에 그 3개의 정점이 진짜 삼각형 인지 확인하기 위해서 마지막 정점에서 다시 시작 정점으로 갈 수 있는지 확인하는 조건을 추가하였고 조건을 만족하면 삼각형 개수가 늘어난다.

 

아래는 gpt 가 준 풀이로

def count_triangles(n, edges):
    g = [[] for _ in range(n + 1)]
    
    # 그래프 생성
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)
    
    triangle_count = 0
    
    # 모든 i, j, k에 대해 삼각형을 체크
    for i in range(1, n + 1):
        for j in g[i]:
            if j > i:  # i < j인 경우만 고려
                for k in g[j]:
                    if k > j and i in g[k]:  # i < j < k이면서 (i, k)도 연결된 경우
                        triangle_count += 1

    return triangle_count

# 테스트 케이스 입력
test = int(input())
for t in range(1, test + 1):
    n, m = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    
    # 결과 출력
    result = count_triangles(n, edges)
    print(f"#{t} {result}")