/<> 백준 1058번 : 친구 (C언어)

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

 

 

노가다 느낌으로 두 사람을 기준으로 나머지 사람들을 탐색해 서로 친구먹고 있으면 2-친구로 간주하면 되겠다고 생각했는데, 후에 보니 플로이드-워셜(Floyd-Warshall) 알고리즘이었더군요.. (아니 지지난달에 학교에서 배운건데 그새 까먹었네)

 

 

1. 입력에 따라 이차원 배열을 저장합니다. 이 때 Y이면 1, N이면 inf 를 저장합니다. inf 는 구분이 가능한 아주 큰 숫자나 음수로 설정하면 됩니다.

 

2. 반복문을 통해 서로 공유하는(?) 친구가 있으면 배열의 값을 바꿉니다. 이 때 inf 를 제외하면 2가 최대입니다. (직접 친구면 이미 1, 경유해서 친구면 2)

 

3. 각 사람마다 2-친구의 수를 저장하고, 이 중 최댓값을 구합니다.

 

 

<코드>

#include <stdio.h>
#define inf 9999999

int n;
int friend[50][50];
int two_count[50] = {0,};

void two_friend() {
        for(int k = 0; k < n; k++) {
                for(int i = 0; i < n; i++) {
                        for(int j = 0; j < n; j++) {
                                if(i != j && j != k && k!= i) {
                                        if(friend[i][j] > friend[i][k] + friend[j][k]) friend[i][j] = friend[i][k] + friend[j][k];
                                }
                        }
                }
        }
}

int main() {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
                char NY[50];
                scanf("%s", NY);
                for(int j = 0; j < n; j++) {
                        if(NY[j] == 'Y') friend[i][j] = 1;
                        else friend[i][j] = inf;
                }
        }

        two_friend();

        int max = 0;
        for(int i = 0; i < n; i++) {
                int count = 0;
                for(int j = 0; j < n; j++) {
                        if(i != j) if(friend[i][j] <= 2) two_count[i]++;
                }

                if(max < two_count[i]) max = two_count[i];
        }

        printf("%d\n", max);
        return 0;
}