[G4] 백준 10159번 저울 C++ 플로이드 와샬

리뷰

 

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

방향 그래프에서 노드별로 경로상 연결된 노드의 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• d : 노드간 연결 여부를 저장할 2차원 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 d배열을 초기화한다.
2. 플로이드 와샬 알고리즘을 통해 특정 노드를 통해 다른 노드에 갈 수 있으면 d배열에 해당 노드간 연결 처리를한다.
3. 1번 노드부터 순회하며 변수 cnt를 매번 0으로 초기화한다.
4. 한번 더 1번 노드부터 순회하며 자신과 동일 노드인 경우 continue처리한다.
5. 두 노드 간 간선이 아예 존재하지 않을 경우 cnt를 증가시킨다.
6. cnt를 출력하고 개행문자를 삽입한다.
7. 위 로직을 모든 노드를 순회할때까지 반복해준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이므로 노드가 작아 플로이드 와샬 알고리즘이 효과적이다.
2. 그래프에서 사이클은 발생하지 않는다고 정의되어있다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 101;
int n, m;
bool d[N][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		d[a][b] = true;
	}

	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (!d[i][k] || !d[k][j]) continue;
				d[i][j] = true;
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		int cnt = 0;

		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;
			if (!d[i][j] && !d[j][i]) ++cnt;
		}

		cout << cnt << "\n";
	}
}