백준 BOJ 2458 - 키 순서

https://www.acmicpc.net/problem/2458

2458번: 키 순서

DFS로 해결했다.

각 학생마다 DFS를 한번씩 돌면서 순회를 하는데,

이때 자기 자신을 포함해서 갈 수 있는 노드의 갯수를 세준다.

이 수에서 1을 뺀 것이 자기 자신보다 키가 큰 학생의 수이고,

 

DFS 순회 과정에서 A에서 B로 갈수 있을경우 chk[B][A]에 기록해둔 뒤,

마지막에 chk[K] 배열 속의 모든 수들을 더해주고 1을 빼면

어떠한 위치에서 B로 올 수 있는 경우의 개수, 즉 자기 자신보다 키가 작은 학생의 수를

구할 수 있다.

 

당연한 이야기지만 중복으로 세지 않도록 체크는 해줘야 한다.

 

M이 그렇게 크지 않아서 시도해봄직했던 방법.

 

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

int taller[567] = {0};
int shorter[567] = {0};
bool chk[567][567] = {0};
bool vis[567] = {0};

vector<int> g[567];

int count(int cnt, int now){
	chk[now][cnt] = true;
	vis[now] = true;
	
	int ret = 1;
	for(auto nxt : g[now]){
		if(!vis[nxt]) ret += count(cnt,nxt);
	}
	return ret;
}

int main(){
	int N,M,a,b;
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> a >> b;
		g[a].push_back(b);
	}
	
	for(int i=1; i<=N; i++){
		memset(vis, 0, sizeof(vis));
		taller[i] = count(i,i);
	}
	
	int ans = 0;
	for(int i=1; i<=N; i++){
		for(int j=0; j<567; j++) shorter[i] += chk[i][j];
		
		if((taller[i]-1) + (shorter[i]-1) == N-1) ans++;
		//printf("[%d - %d %d]\n", i, taller[i]-1, shorter[i]-1);
	}
	cout << ans;
	return 0;
}