백준 10159 저울

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

10159번: 저울

백준의 '여행 가자'라는 문제랑 흡사하다.

 

이 문제도 두 가지 버전으로 풀 수 있다.

첫 번째가 BFS, 두 번째가 플로이드 와샬 이다.

 

우선 BFS부터 살펴보자.

 

이 그래프는 단방향 그래프이고 양방향이 절대 될 수 없을 뿐더러 사이클도 생길 수 없기 때문에 

 

트리구조다. 그래서 한 정점에서 BFS를 돌릴 때 접근되는 모든 점은 시작 정점보다 가볍다. 

 

이 때 주의할 건 'A가 B보다 가볍다' 라는 건 A의 관점에서 B와의 대소 관계를 파악할 수 있고, 또한 B의 관점에서도 A와의 대소 관계를 파악할 수 있다는 점이다. 이를 유의하면서 코드를 짜면 아래와 같다. 

 

/* 저울 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

void input();
void solve();
	
int N, M, dp[100 + 1];
vector<int> edge[100 + 1];


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		edge[a].push_back(b);
	}
}

void bfs(int idx) {
	queue<int> q;
	q.push(idx);

	bool is_visit[100 + 1] = { false, };
	is_visit[idx] = true;
	dp[idx] ++;

	while (!q.empty()) {
		int curr = q.front();
		q.pop();

		for (auto i : edge[curr]) {
			if (is_visit[i] == false) {
				is_visit[i] = true;
				q.push(i);
				dp[idx]++;
				dp[i]++;
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= N; i++) {
		bfs(i);
	}

	for (int i = 1; i <= N; i++) {
		cout << N - dp[i] << "\n";
	}
}

 

두 번째는 플로이드 워셜 알고리즘이다.

/* 저울 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

void input();
void solve();
	
int N, M;
bool edge[100 + 1][100 + 1];


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		edge[a][b] = true;
	}
}

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (edge[j][i] == true && edge[i][k] == true) {
					edge[j][k] = true;
				}
			}
		}
	}
	
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (!edge[i][j] && !edge[j][i]) cnt++;
		} 
		cout << cnt - 1 << '\n';
	}
}