BOJ (C/C++) 1058번: 친구

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

1058번: 친구

---

풀이

i와 j가 친구일 때, j와 친구인 k도 i와 친구이다.F배열의 값을 바꾸면 예제 4의 답이 틀리게 나와서 2-친구 관계를 표현한 visited배열을 추가함.

---

코드

#include <stdio.h>
bool F[50][50], visited[50][50];

int Friend(int now, int N) {
	int max = 0, cnt;
	for (int i = 0; i < N; i++) {
		cnt = 0;
		for (int j = 0; j < N; j++) {
			if (F[i][j]) {
				visited[i][j] = true;
				for (int k = 0; k < N; k++) {
					if (F[j][k] && i != k) visited[i][k] = true;
				}
			}
		}
		// 친구 수 구하기
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) cnt++;
		}
		if (max < cnt) max = cnt;
	}
	return max;
}
int main() {
	int N;
	char c[51];
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", c);
		for (int j = 0; j < N; j++) {
			if (c[j] == 'Y') F[i][j] = visited[i][j] = true;
		}
	}
	printf("%d", Friend(0, N));
	return 0;
}