SWEA 6057 그래프의 삼각형(with Python)
내가 생각하는 Solution
-
난 다른 사람에 비해서 너무 어렵게 접근해서 풀었다...
-
문제를 조금 더 쉽게 생각하는 힘을 길러야할 듯...
문제에서 생각해볼 점
-
노드(
node
)를 하나씩 순회합니다. -
해당 노드와 연결된 노드(
neighbor
)를 순회합니다. -
neighbor
와 연결된 노드(n_neighbor
)를 순회하면서n_neighbor
가node
에 포함되는지 확인합니다. (count 하기) -
이렇게하면 테스트 케이스 기준으로 ([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}')
Author And Source
이 문제에 관하여(SWEA 6057 그래프의 삼각형(with Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@daeungdaeung/SWEA-6057-그래프의-삼각형with-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)