(BOJ) 10159 저울

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

문제 풀이:

- 플로이드 와샬 알고리즘 이용

- 입력 값을 단방향으로 이동 가능하다고 생각 

  ex) 

6
5
1 2   // 1->2로 이동 가능
2 3   // 2->3으로 이동 가능
3 4   // ...
5 4
6 5

- a->b로 못가고 b->a로도 못 가면 비교 못 하는 것 -> cnt++

소스 코드:

#include <iostream> #include <queue> #include <vector> #include <string.h> #include <algorithm> #define inf 1000000 using namespace std; int n, k,dist[101][101]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> k; for (int i = 1; i <= n; i++) { fill(dist[i], dist[i] + n + 1, inf); } for (int i = 0; i < k; i++) { int a,b; cin >> a>>b; dist[a][b] = 0; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } for (int i = 1; i <= n; i++) { int cnt = 0; for (int j = 1; j <= n; j++) { if (i!=j&&dist[i][j] == inf && dist[j][i]==inf) cnt++; } cout << cnt << '\n'; } return 0; }