[BOJ] 백준 16721 Structure of Balanced Networks

문제 링크

https://www.acmicpc.net/problem/16721

메모리 제한이 16 MB다.

1번 풀이) 문제에서 준 조건을 활용한다.

2번 풀이) 비트 마스킹으로 모든 쌍의 관계를 저장한다.

1번 풀이)

문제에서 주어진 그래프는 완전그래프이고, 모든 triad가 balanced인 그래프(문제에서 주어짐)이다.

이 말인즉슨, 임의의 노드 X와 임의의 서로 다른 두 노드 A, B에 대해, X-A, X-B의 관계를 각각 알고 있으면 A-B의 관계도 알 수 있다.

따라서 우리는 한 노드 X를 기준으로 X와 다른 노드들간의 관계만 저장해주면 모든 관계를 구할 수 있게 된다.

2번 풀이)

는 설명할 게 없으니 코드로만 올리겠습니다.

정답 코드

1번 풀이)

2번 풀이)