백준 2458(키 순서) c++

문제

2458번: 키 순서

n개의 사람과 m개의 키 순서가 주어지면 자신의 키 순서를 정확히 알 수 있는 사람의 수를 세는 문제 입니다.

예를 들어 입력이 3 4가 나오면 3번 사람이 4번 사람보다 작다는 의미입니다.

키 순서를 바탕으로 그래프를 만들면 다음과 같이 만들어 집니다.

여기서 4번만 자신의 키 순서를 정확히 알 수 있습니다.

 

처음에 생각한 방법은 dfs입니다.

1번 노드부터 n번 노드까지 차례로 dfs를 진행하면서 모든 노드를 방문하면 그 노드는 자신의 키 순서를 정확히

알 수 있습니다. 

하지만 그래프의 방향이 양방향이 아니라 한 방향이기 때문에 자신보다 키가 작은 노드의 방문 여부를

알 수 없었습니다.

 

힌트를 얻은 것이 그래프 정보를 하나의 벡터에 저장하는 것이 아니라

자신 보다 키가 큰 벡터, 자신 보다 키가 작은 벡터를 선언해 각각 dfs를 진행해, 방문 갯수가 n-1 이면

모든 노드를 방문한 것이므로 방문 갯수가 n-1이면 답을 ++ 해주어서 정답을 출력합니다.

vector<int>up[501];
vector<int>down[501];

int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	up[a].push_back(b); // a<b
	down[b].push_back(a); // b>a
}

up 벡터와 down 벡터를 선언해 주었습니다. 

int ans = 0;
for (int i = 1; i <= n; i++) {
	memset(check, false, sizeof(check));
	cnt = 0;
	dfs(up, i);
	dfs(down, i);
	if (cnt == n - 1)ans++;
}

cout << ans;

dfs를 각 노드마다 2번씩 진행해 주어 cnt를 세어주고 cnt가 n-1이면 ans를 늘려주었습니다.

void dfs(vector<int>v[],int s) {
	check[s] = true;
	for (auto nxt : v[s]) {
		if (check[nxt])continue;
		cnt++;
		dfs(v, nxt);
	}
}

dfs 부분은 평소 dfs부분과 동일합니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll = long long;
vector<int>up[501];
vector<int>down[501];
bool check[501];
int cnt;
void dfs(vector<int>v[], int s);
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		up[a].push_back(b); // a<b
		down[b].push_back(a); // b>a
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		memset(check, false, sizeof(check));
		cnt = 0;
		dfs(up, i);
		dfs(down, i);
		if (cnt == n - 1)ans++;
	}

	cout << ans;


	return 0;
}
void dfs(vector<int>v[],int s) {
	check[s] = true;
	for (auto nxt : v[s]) {
		if (check[nxt])continue;
		cnt++;
		dfs(v, nxt);
	}
}