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

February 27, 2022

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

1. 문제Permalink

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

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

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

boj-24542

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

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

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

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

boj-24542

	#include <bits/stdc++.h>
	using namespace std;

	#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
	#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
	#define ll long long int
	#define pii pair<int, int>
	#define PQ priority_queue
	#define LEN(v) int(v.size())
	#define ALL(v) v.begin(),v.end()
	#define INF 2e9
	#define LINF 1e18
	#define MAX 200001
	#define MOD 1000000007

	vector<bool> visited(MAX, 0);
	vector<vector<int>> Edge(MAX, vector<int>());

	ll DFS(int node) {
	ll cnt = 1;
	for (int next : Edge[node]) {
	if (visited[next]) continue;
	visited[next] = 1;
	cnt += DFS(next);
	}
	return cnt;
	}

	int main() {
	FASTIO;
	int N, M;
	cin >> N >> M;
	FOR(m, 1, M) {
	int u, v;
	cin >> u >> v;
	Edge[u].push_back(v);
	Edge[v].push_back(u);
	}
	ll ans = 1;
	FOR(i, 1, N) {
	if (visited[i]) continue;
	visited[i] = 1;
	ans = (ans * DFS(i)) % MOD;
	}
	cout << ans;

	return 0;
	}