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

📌문제

💪아이디어

1. 그래프 간선 표시하기
   
   defaultdict을 사용하여 key값은 노드 value값은 노드와 연결된 다른 노드를 추가하는 형식으로 그래프 간선을 표시하였다. 이차원배열을 사용하여 표현할 수도 있었지만 2.에서 노드 조합을 찾을때 defaultdict이 for문을 돌면서 더 직관적이라 판단되었다.
   
   
2. 노드간의 연결된 간선따라가기
   
   노드에 연결된 간선을 따라가는 방식을 dfs를 사용하여 구현하였다. 삼각형은 간선이 3개이고 문제에서 제시한 노드의 값은 ‘i < j < k’인 크기를 가진다. 따라서 간선이 3개미만일 경우에는 마지막 노드가 연결된 노드보다 작으면 선택하는 방법을 사용하였다.
   
   
3. 삼각형인지 체크하기
   
   간선이 3개가 되면 첫 번째 노드와 마지막 노드가 같은지 검사해야한다. 마지막노드가 i이어야 사이클이 생겨서 삼각형이 되는데 2.에서 추가되는 노드가 마지막에 선택한 노드보다 크다고 설정하면 i가 선택될 수 없었다.(i는 k보다 작기때문에) 따라서 간선이 3개일경우 따로 마지막에 선택된 노드와 연결된 노드가 첫번째에 선택된 노드가 같으면 삼각형이라 판단하여 answer값을 하나씩 올리도록하였다. 문제에 같은 간선은 표시되어있지 않다고 써져있기 때문에 중복된 삼각형을 찾지 않아도 된다.
   
   

🥂코드

from collections import defaultdict
def dfs(inx,li):
    global answer
    for nxt_node in graph[inx]:
        if len(li)<3:
            if inx<nxt_node:
                li.append(nxt_node)
                dfs(nxt_node,li)
                li.pop()
        else:
            if li[0]==nxt_node: answer+=1
                
T=int(input())
for test_case in range(1,T+1):
    n,m=map(int,input().split())
    graph=defaultdict(list)
    answer=0
    for _ in range(m):
        x,y = map(int,input().split())
        graph[x].append(y)
        graph[y].append(x)
    for i in range(1,n+1): dfs(i,[i])
    print('#'+str(test_case)+' '+str(answer))