백준 1058 c++ "친구" -[PlusUltraCode]

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

1058번: 친구

[필자 사고]

플로이드 와샬 알고리즘이다.

 

플로이드 와샬 알고리즘의 중요한 특징이 있다.

 

문제에서 그래프로 주어 졌을때랑 2차원 배열로 주어 졌을때는 조금의 차이점이 있다.

 

먼저 그래프이다.

 

와샬 알고리즘 사용 후 1->4의 값이 자연수고 4->1 이 값이 무한대일 경우 1과 4의 관계가 형성 되었기 때문에

 

4->1의 값 또한 변경해줘야 된다. 

 

반면에 배열로 주어졌을 경우 후속조취 없이 바로 와샬 알고리즘을 사용하면 해결 된다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> Arr;
int N;

const int INF = 987654321;

void Print() {
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			cout << Arr[i][k] << " ";
		}
		cout << '\n';
	}
}
void Input() {
	cin >> N;
	Arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1, INF);
	}
	string str;
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int k = 0; k <str.size(); k++) {
			if (str[k] == 'N') {
				Arr[i][k + 1] = INF;
			}
			else {
				Arr[i][k + 1] = 1;
			}
		}
	}
	for (int i = 0; i <= N; i++) {
		Arr[i][i] = 0;
	}
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				Arr[s][e] = min(Arr[s][e], Arr[s][k] + Arr[k][e]);
			}
		}
	}
	
	
}



int main(void) {
	Input();
	Floyd_Warshall();
	int maxNum = -1;
	for (int i = 1; i <= N; i++) {
		int count = 0;
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k]<=2&&i!=k) {
				count++;
			}
		}
		if (maxNum < count) {
			maxNum = count;
		}
		
	}
	cout << maxNum;
}