백준 2458 키순서

www.acmicpc.net/problem/2458

2458번: 키 순서

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.tie(NULL);

	int n, m;//n=학생수 m=비교수

	cin >> n >> m;

	vector <vector <int>>arr(501, vector<int>(501,0)); //501열 빈 벡터 2차원 배열 선언+초기화

	int x, y;

		for (int j = 1; j <= m; j++)
		{
			cin >> x >> y;
			arr[x][y] = 1;//가는길이 있음을 표시
		//	arr[y][x] = 1;//가는길이 있음을 표시
		}
	
	//플로이드와샬인지 뭔지

	for (int i = 1; i <= n; i++) //중간점
	{
		for (int j = 1; j <= n; j++) //출발
		{ 
			for (int k = 1; k <= n; k++) //도착
			{
				if (i == j || j == k || i == k)continue; //자기 스스로의 길은 의미가 없어 시간복잡도를 조금이나마 최소화

				if (arr[j][i] == 1 && arr[i][k]==1)arr[j][k] = 1;


			}
		}
	}


	int stuNum=0;

	for (int i = 1; i <= n; i++)
	{
		int cNt = 0;
		for (int j = 1; j <= n; j++)
		{
			if (arr[i][j]  == 1||arr[j][i])cNt++;
		}
		if (cNt == n - 1)
			stuNum++;


	}
	cout << stuNum;
}

플로이드 와샬을 공부하며 사용해 보았다

 

곰곰히 다른 블로그들을 돌아다니며 플로이드 와샬 정리글을 보고 있자니, 다들 쉽다는데 뭐가 쉬운지 나는 도저히 모르겠다 ㅠㅠ

 

그래도 공통적으로 반복문 3개를 통하여 완전탐색하고

다시보니 너무나도 당연한 말 같았지만 저때 간과한게 가운대가 출발점 마지막이 도착점 맨 위는 중간점임을 간과하여 애를 먹었다

 

길이 있음은 1로 표시하였고

인원수-1(본인을 제외) 만큼의 1이 있다면, 본인의 위치를 정확히 알 수 있는 방법이였다

 

++플로이드와샬은 for문이 3번 돌아가므로 ^3가 되버리기에 비교군이 너무 클 경우 사용하기 힘들다  !