백준 1058번 친구

문제 링크입니다: https://www.acmicpc.net/problem/1058

전형적인 플로이드-와샬 알고리즘 문제였습니다.

우선, 자기 자신은 친구가 될 수 없기 때문에 i==j일 때는 0, 'Y'일 때는 1, 그리고 'N'일 때는 INF를 입력합니다.

이후에는 플로이드 알고리즘을 수행한 뒤 모든 사람의 친구의 수를 세는데,

1. 서로 친구이거나

2. 한 다리 건너서 아는 친구

까지 세기 때문에 friendsList[i][j]<=2인 수를 세고 여기서 최대 값을 출력합니다!

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 50;

 

int N;

int friendsList[MAX][MAX];

 

//전형적인 플로이드-와샬 알고리즘

void floyd(void)

{

        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 || i == k)

                                          continue;

                                 else if (friendsList[i][j] > friendsList[i][k] + friendsList[k][j])

                                          friendsList[i][j] = friendsList[i][k] + friendsList[k][j];

                         }

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 string temp;

                 cin >> temp;

 

                 for (int j = 0; j < temp.size(); j++)

                 {

                         if (i == j)

                                 friendsList[i][j] = 0;

                         else

                                 friendsList[i][j] = temp[j] == 'Y' ? 1 : INF;

                 }

        }

 

        floyd();

 

        int result = 0;

 

        for (int i = 0; i < N; i++)

        {

                 int cnt = 0;

 

                 for (int j = 0; j < N; j++)

                 {

                         if (i == j) //자기 자신은 친구가 될 수 없다

                                 continue;

                         else if (friendsList[i][j] <= 2) //2-친구의 수를 센다

                                 cnt++;

                 }

                 result = max(result, cnt);

        }

       

        cout << result << endl;

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~