[BOJ 24542] 백준 24542번 - 튜터-튜티 관계의 수

		2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 풀이
A		[BOJ 24542] 튜터-튜티 관계의 수
C		[BOJ 24544] 카카오뷰 큐레이팅 효용성 분석
D		[BOJ 24545] Y
G		[BOJ 24548] 도로 정보
K		[BOJ 24552] 올바른 괄호
L		[BOJ 24553] 팰린드롬 게임

1. 문제

$24542$. 튜터-튜티 관계의 수 (2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter) Open Contest A번)

백준 24542번 - 튜터-튜티 관계의 수 (https://www.acmicpc.net/problem/24542)

2. 풀이

양방향(=방향이 정해지지 않은) 여러 개의 트리가 주어진다. (문제에서는 사이클이 없는 형태의 양방향 그래프 하나라고 서술했다. 따라서 반드시 모든 노드가 이어져 있음은 보장되지 않으므로 여러 개의 트리의 집합체라고 볼 수 있다.)

이 그래프의 모든 간선의 방향을 결정하는 경우의 수를 구하는 문제이다. 이때, 최초로 교육 자료를 받는 인원 수가 최소가 되도록 간선의 방향을 결정해야 한다.

그림처럼 하나의 트리가 주어진다고 가정하자. 하나의 정점을 정해서 그 정점에서 모든 노드로 갈 수 있도록 간선의 방향을 설정하면, 처음에 정한 정점만 최초로 교육 자료를 받으면 된다.

따라서, 하나의 트리에 대해서 최초로 교육 자료를 받는 인원이 최소가 되는 방법의 수는 그 트리의 노드 수와 같다.

문제의 그래프는 여러 개의 트리로 이루어져 있다. 따라서, 총 경우의 수(정답)는 각 트리의 노드 수를 모두 곱한 값이다.

어떤 방식으로든 각각의 트리(연결된 노드 집합)의 노드 개수를 세서 모두 곱하면 정답을 구할 수 있다.

3. 채점 결과

4. 회고

.

5. 코드