[BOJ] 1058 - 친구

Sierra·2022년 1월 24일

[BOJ] GraphTheory

목록 보기

8/30

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

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

예제 입출력

예제 입력 1

3
NYY
YNY
YYN

예제 출력 1

예제 입력 2

3
NNN
NNN
NNN

예제 출력 2

예제 입력 3

5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN

예제 출력 3

예제 입력 4

10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN

예제 출력 4

예제 입력 5

15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

예제 출력 5

Solution

#include <bits/stdc++.h>
#define MAX 51
#define INF 987654321
using namespace std;

vector<int> vec[MAX];
int MATRIX[MAX][MAX];
int N;
void floydwarshall(){
    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (MATRIX[i][k] != INF && MATRIX[k][j] != INF){
                    if(i == j) continue;
                    else MATRIX[i][j] = min(MATRIX[i][j], MATRIX[i][k] + MATRIX[k][j]);
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string tmp;
    int answer = 0;
    cin >> N;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++) MATRIX[i][j] = INF;
    }
    for(int i = 1; i <= N; i++){
        cin >> tmp;
        for(int j = 0; j < N; j++){
            if(tmp[j] == 'Y'){
                MATRIX[i][j+1] = 1;
            }
        }
    }
    floydwarshall();
    for (int i = 1; i <= N; i++){
        int count = 0;
        for (int j = 1; j <= N; j++){
            if(MATRIX[i][j] <= 2) count++;
        }
        answer = max(answer, count);
    }
    cout << answer << '\n';
}

전형적인 플로이드 와샬 문제다. 2-친구가 되는 조건을 다시 한번 살펴보자.

어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다.

우리는 이 2-친구가 가장 많은 양반을 찾으면 된다.
친구들 간의 관계를 살펴보았을 때, 하나의 관계의 연결 비용이 1이라고 가정하면, 우리는 이 관계간의 상관관계를 찾아서 2 이하의 연결고리를 가진 친구들의 데이터를 살펴보면 된다.

즉 A와 C가 친구이고 B와 C가 친구라면 A와 B는 연결될 수 있다.

if (MATRIX[i][k] != INF && MATRIX[k][j] != INF){
    if(i == j) continue;
    else MATRIX[i][j] = min(MATRIX[i][j], MATRIX[i][k] + MATRIX[k][j]);
}

이 부분을 주목해보자. i와 k 사이에 상관관계가 있고 k와 j간에 상관관계가 있다면, i와 j 간에 상관관계가 있을 수 있다는 것이다. 만약 i와 j가 친구가 아니더라도 (INF 값이더라도) 플로이드 와샬 알고리즘을 통해 2라는 값을 가질 수 있게 된다.

for (int i = 1; i <= N; i++){
    int count = 0;
    for (int j = 1; j <= N; j++){
        if(MATRIX[i][j] <= 2) count++;
    }
     answer = max(answer, count);
}
cout << answer << '\n';