백준 1058 - 친구(C++)

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

1058번: 친구

플로이드 와샬을 이용해 푸는 문제입니다.

2-친구를 찾는 문제입니다.

2-친구가 되기 위해서는 X와 Y가 서로 친구이거나, X와 Y가 한다리 건너서 이어져 있으면 됩니다.

 

X에 대해 남은 사람들이 몇번을 건너서 친구가 될 수 있는지를 확인하기 위해서 플로이드 와샬 알고리즘을 이용하면 됩니다.

 

플로이드 와샬 알고리즘을 사용한 후, Distance[i][j]의 값이 2이하라면, 2-친구를 만족한다는 것입니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N;
int Distance[51][51];

void reset_distance(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            Distance[i][j] = INF;
        }
    }
}

void floyd_warshall(){
    for(int i = 1; i <= N; i++){ // i를 경유해
        for(int j = 1; j <= N; j++){
            for(int k = 1; k <= N; k++){ // j에서 k로 간다.
                if(Distance[j][i] != INF && Distance[i][k] != INF && j != k){
                    // j -> i + i -> k의 값과 기존의 값을 비교한다.
                    // 값을 비교하기 위해 배열에 값이 존재하는지부터 확인한다.
                    // j와 k는 같으면 안되기에 조건에 추가해준다.
                    Distance[j][k] = min(Distance[j][k], Distance[j][i] + Distance[i][k]);
                }
            }
        }
    }
}

void solve(){
    int ans = 0;
    floyd_warshall();
    for(int i = 1; i <= N; i++){
        int cnt = 0;
        for(int j = 1; j <= N; j++){
            //거리가 2인 친구를 찾는다.
            if(Distance[i][j] <= 2) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    reset_distance();
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            char x;
            cin >> x;
            if(x == 'Y'){
                if(Distance[i][j] > 1) Distance[i][j] = 1;
            }
        }
    }
    solve();
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N;
int Distance[51][51];

void reset_distance(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            Distance[i][j] = INF;
        }
    }
}

void floyd_warshall(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            for(int k = 1; k <= N; k++){
                if(Distance[j][i] != INF && Distance[i][k] != INF && j != k){
                    Distance[j][k] = min(Distance[j][k], Distance[j][i] + Distance[i][k]);
                }
            }
        }
    }
}

void solve(){
    int ans = 0;
    floyd_warshall();
    for(int i = 1; i <= N; i++){
        int cnt = 0;
        for(int j = 1; j <= N; j++){
            if(Distance[i][j] <= 2) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    reset_distance();
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            char x;
            cin >> x;
            if(x == 'Y'){
                if(Distance[i][j] > 1) Distance[i][j] = 1;
            }
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요