취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1058번 문제인 친구이다.
문제는 아래 링크를 확인하자.

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

각 사람을 노드로, 노드 사이의 에지를 서로 친구관계이면 가중치 1, 아니라면 가중치 무한대인 그래프에서 각 사람끼리의 거리를 구해 거리가 1 또는 2인 사람들을 찾는 것으로 문제를 해결할 수 있다.

이를 알아낼 수 있는 방법 중 하나는 Floyd-Warshall 알고리즘을 이용하는 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int dist[50][50];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		for (int j = 0; j < N; j++) {
			if (i == j) dist[i][j] = 0;
			else if (s[j] == 'N') dist[i][j] = 999;
			else dist[i][j] = 1;
		}
	}

	//Floyd-Warshall
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int cnt = 0;
		for (int j = 0; j < N; j++) {
			if (0 < dist[i][j] && dist[i][j] < 3) cnt++;
		}
		if (cnt > ans) ans = cnt;
	}

	cout << ans;
}