[백준 10159] 저울

난이도

골드 III

📜문제

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

🔎접근

모든 정점끼리의 무게를 비교해서 모든 정점과 비교가 불가능 한 것의 개수를 구하는 문제이다.

모든 정점에서 모든 정점까지를 비교할 수 있는 것은 플로이드-와샬 알고리즘이다.

🌞풀이

#include <iostream>
#include <algorithm>

#define MAX 101
#define INF 999999999

using namespace std;

int matrix[MAX][MAX];

int vertex, edge;

void Floyd() // 플루이드-와샬 알고리즘
{
	for (int i = 1; i <= vertex; i++)
	{
		for (int j = 1; j <= vertex; j++)
		{
			for (int k = 1; k <= vertex; k++)
			{
				matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k]);
			}
		}
	}

}
int main()
{
	cin >> vertex >> edge;


	for (int i = 1; i <= vertex; i++)
	{
		for (int j = 1; j <= vertex; j++)
		{
			matrix[i][j] = INF; // 초기 배열 INF로 초기화
		}
	}

	int heavy, light = 0;
	for (int i = 0; i < edge; i++)
	{
		cin >> heavy >> light;
		matrix[heavy][light] = 1;
	}

	Floyd();

	for (int i = 1; i <= vertex; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= vertex; j++)
		{
			if (i == j) continue;
			if (matrix[i][j] == INF && matrix[j][i] == INF) cnt++;
		}
		cout << cnt << "\n";
	}

	return 0;
}

핵심

for (int j = 1; j <= vertex; j++)
		{
			if (i == j) continue;
			if (matrix[i][j] == INF && matrix[j][i] == INF) cnt++;
		}

matrix[i][j] 와 matrix[j][i]의 값이 둘다 INF라면 i와 j의 무게 비교를 할 수 없다는것이다.

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기