[BOJ] 14591 KUBC League, 17165 Gosu

14591 KUBC League

문제 요약

토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다.

문제 풀이

DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다!

코드

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;

using namespace std;

int chk[2020];
int adj[2020][2020];
vector<int> ans;

int n;
void dfs(int x) {
	chk[x] = 1;
	for (int i = 1; i <= n; i++)
		if (!chk[i] && adj[x][i]) dfs(i);
	ans.push_back(x);
}

int main() {
	fio();
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> adj[i][j];
	dfs(1);
	cout << ans.size() << endl;
	reverse(all(ans));
	for (int x : ans) cout << x << ends;
}

17165 Gosu

문제 요약

토너먼트 그래프가 있다. 어떤 정점 x의 태보 레벨을 x에서부터의 다른 정점까지의 최단경로 길이 중 최댓값이라고 정의하자. 이때 가장 태보 레벨이 작은 사람과 그 때의 태보 레벨을 구해야 한다.

문제 풀이

잘 생각해 보면 태보 레벨의 최댓값이 그렇게 길지 않을 것 같고, 실제로 레벨이 3 이상이 될 수 있다고 가정하고 귀류법을 걸면 모순이다. (또한 이 때 태보 레벨이 가장 작은 사람은 outdegree가 가장 큰 사람이다.) 따라서 한 사람이 모두를 이길 수 있으면 태보 레벨은 1, 아니라면 2이다. 코드는 이걸 미처 깨닫지 못해 더 복잡하게 작성되어 있다.

코드

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;

using namespace std;

string adj[3005];
int dist[3005], win[3005];

int main() {
	fio();
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> adj[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			win[i] += adj[i][j] == 'W' ? 1 : 0;
	int ma=0, mai=0;
	for (int i = 0; i < n; i++)
		if (win[i] > ma)
			ma = win[i], mai = i;
	queue<int> Q; Q.push(mai); dist[mai] = 1;
	while (!Q.empty()) {
		int hr = Q.front(); Q.pop();
		for (int i = 0; i < n; i++) {
			if (dist[i] || adj[hr][i] != 'W') continue;
			dist[i] = dist[hr] + 1;
			Q.push(i);
		}
	}
	ma = *max_element(dist, dist + n);
	cout << ma - 1 << ends << mai + 1;
	return 0;
}