백준 Baekjoon 10159 저울 풀이

사용언어

Visual studio 2019 C++

생각하기

플로이드 워샬 알고리즘 사용

플로이드 워샬 알고리즘

모든 정점들 사이의 최단경로를 구하는 알고리즘.

[11404 풀이]

#include <iostream>
using namespace std;
const int MAX = 100 + 1;
int N, M;
int juwul[MAX][MAX];

void floyd() {
	for (int i = 1; i <= N; i++) { // 중간
		for (int j = 1; j <= N; j++) { // 처음
			for (int k = 1; k <= N; k++) { // 끝
				if (juwul[j][k] == 0) {
					if (juwul[j][i] == 1 && juwul[i][k] == 1)
						juwul[j][k] = 1;
					else if (juwul[j][i] == -1 && juwul[i][k] == -1)
						juwul[j][k] = -1;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		juwul[a][b] = 1; // a > b
		juwul[b][a] = -1; // b가 a보다 작음
	}

	floyd();

	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (i == j)
				continue;
			if (juwul[i][j] == 0)
				cnt++;
		}
		cout << cnt << "\n";
	}
}