[BOJ1058 C++] 친구

문제 링크

흠 .. 실버2 문제인데 오히려 쉬웠는데 ..

딱보면 뭔가 그래프 냄새 솔솔 나는 문제인데.. 그래프로 풀면 어려운 문제?라고 느꼈다.

그냥 예전에 썼던 기술인 array만들어놓고 친구로 체크 했으면 1 아니면 0으로 해서 중복 피하고

2-연결 친구라고 하는 것들을 구하면 된다.

여기서 문제였던게 string을 여러개 받는데 ..

string *string_arr;

인트마냥 요딴 짓 하면 큰일난다 .. 컴파일은 이상하게 되고 문제 없이 들어가는데

다른 변수의 메모리에 침범을 지맘대로 하는지 다른 것들이 개박살나더라

vector<string> strings;

이렇게 하면 얼마나 편해 바보

그리고 문제가 좀 불친절하다는 질문 글도 있었는데 솔직히 ㅇㅈ

A의 2연결 친구가 되기 위해선
1. A와 direct로 연결되어 있는 친구들
2. 추가로 그 친구들의 친구들 중 A와 친구가 아닌 친구

이제 여기서 중복이 생길 수 있다고 느낄 수 있는데,

A -> B로 연결되어 있고, A -> C로 연결되어 있을때

B -> C도 친구일 경우, 코드 상 A->B가 친구면 B의 친구들을 살필텐데,

B-> C와 친구기 때문에 +1 해버렸다가는,

나중에 A->C 친구 검사할 때 중복으로 카운트 될 수 있다.

게다가 B->A친구, B->C 친구일 때 A->D 가친구고 C ->D도 친구면

중복 신경 안쓰면

B->A->D 도 카운트 되고 B->C->D 도 카운트 된다.

그래서 이미 카운트 한거는 int array 에다가 1로 마킹!

B->A->에서 B->D의 2연결을 세고 나서

[B][D] 는 이미 1로 되어있으면

B->C->D의 B->D 2연결은 안 센다.

그러면 중복을 피할 수 있지!

..너무 무식한가

//
// Created by 신성준 on 2023/02/27.
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    vector<string> arr;
    int **friend_arr = new int *[N];
    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        arr.push_back(s);
        friend_arr[i] = new int[N];
    }

    int max_relation = 0;
    for(int i =0; i < N; i++){
        int relation = 0;
        for(int j=0; j < N; j++){
            if(arr[i][j] == 'Y' && i != j){ //direct friend
                relation++;
                string direct_friend = arr[j];
                for(int k =0; k < N; k++){ //direct friend의 친구들 중, A와 친구 아닌 애들 가져오기 (2연결 친구인지 뭔지)
                    if(direct_friend[k] == 'Y' && arr[i][k] == 'N' && i != k && friend_arr[i][k] != 1){
                        friend_arr[i][k] = 1; //중복 피하기!
                        relation++;
                    }
                }
            }
        }

        if(relation > max_relation){
            max_relation = relation;
        }
    }
    cout << max_relation;
    return 0;
}