[백준]10159 저울(c++)

백준 10159 저울

1. 문제

문제링크

2. 접근법

• 문제 접근
  - 각 물건에 대해서 그 물건과 비교 결과를 알 수 없는 물건의 개수를 출력해야 하므로 2차원 배열을 이용한다. 즉 플로이드 와샬 알고리즘을 사용하는 문제이다.
  - 앞의 물건이 뒤의 물건보다 더 무거우므로 물건을 입력받을 때,
  a보다 b가 무거우면 1, 그 반대인 경우에는 -1로 셋팅해준다.
  - 노드를 추가로 생성하여 삼중 for문을 돌리면서 거쳐가는 노드에 해당하는 값이 찾고자하는 물건의 무게와 같은 경우, 그리고 0이 아닌 경우에 해당 값을 업데이트 해준다.
  - 출력을 위해 이중 for문을 돌리면서 ans값에는 본인을 제외한 값을 초기값으로 셋팅해주고 0이 아닌 경우에 ans를 줄인 후, 마지막으로 ans를 출력시킨다.

3. 코드

#include <algorithm>
#include <iostream>

using namespace std;

int map[101][101];
//floyd-warshall 알고리즘 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, a, b, ans; 

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = -1;
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (map[i][k] == map[k][j] && map[i][k] != 0)
					map[i][j] = map[i][k];
 			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		ans = N - 1;
		for (int j = 1; j <= N; j++)
		{
			if (map[i][j] != 0)
				ans--;
		}
		cout << ans << "\n";
	}
	return 0;
}

4. 시간복잡도

플로이드 와샬 알고리즘은 기본적으로 삼중 for문을 돌리므로 O(N^3)의 시간복잡도를 가진다.
여기서는 시간제한이 1초인데 N값이 최대 100이므로 1000000, 즉 100만이 되어 1억을 넘지 않는다.
따라서 1초이내로 구현이 가능하다.

5. 결과