[백준] 2617 구슬 찾기 - DAG에서의 DFS

문제

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

1. 구슬 2번이 구슬 1번보다 무겁다.
2. 구슬 4번이 구슬 3번보다 무겁다.
3. 구슬 5번이 구슬 1번보다 무겁다.
4. 구슬 4번이 구슬 2번보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.

M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M(1 ≤ M ≤ N(N-1)/2)이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.

 

두 구슬간의 관계가 M번 나옵니다

이때, 한 구슬이 여러번 나올 수도 있으므로 이 관계는 DAG로 표현할 수 있습니다.

따라서 한 구슬보다 확실하게 무겁거나 가벼운 구슬이 N/2개보다 많으면 이 구슬의 무게는 반드시 중간값이 될 수 없습니다.

따라서 그 개수를 세주는 문제입니다.

 

BFS를 사용하면,,, 쉽게 풀 수 있을겁니다

DFS를 사용해 문제를 풀어봤는데 계속해서 오답이 나왔습니다.

 

왜 오답이 나왔나 살펴보니

작성한 DFS에 문제가 있었습니다.

 

int dfs(int c) {
	if (v[c])return v[c];
	v[c] = 1;
	for (int r : adj[c]) {
		v[c] += dfs(r);
	}
	return v[c];
}

처음 작성한 dfs입니다.

메모제이션을 사용하면 시간을 줄일 수 있지않을까 했는데,,

하지만 이런 DAG에서 이런 DFS는 중복을 만듭니다.

만약 1< 2 < 4  ,1< 3 < 4 와 같은 관계가 있을때, 4가 중복해서 들어가게됩니다.

따라서 정직하게(?) 방문표시를 해가면서 더 무겁고, 가벼운 구슬의 개수를 세주면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int N, M, v[100], v2[100], a[100], a2[100];
vi adj[100], adj2[100];

int dfs(int c) {
	if (v[c])return 0;
	v[c] = 1;
	int s = 1;
	for (int r : adj[c]) {
		s += dfs(r);
	}
	return s;
}
int dfs2(int c) {
	if (v2[c])return 0;
	v2[c] = 1;
	int s = 1;
	for (int r : adj2[c]) {
		s += dfs2(r);
	}
	return s;
}
int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		adj2[b].push_back(a);
	}
	REP(i, N) {
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
		adj2[i].erase(unique(adj2[i].begin(), adj2[i].end()), adj2[i].end());
	}
	REP(i, N) {
		mset(v);
		mset(v2);
		a[i]=dfs(i);
		a2[i]=dfs2(i);
	}
	int s = 0;	
	REP(i, N)
		if (a[i] - 1 > N / 2 || a2[i] - 1 > N / 2) s++;
	cout << s;
}