[BOJ] 1058번. 친구 (C++ 17)

 

이 문제를 쉽게 풀어 말하면 다음과 같다.

i번째 사람의 2-친구는,
일단 그의 직계 친구는 일단 내 2-친구고,
직계 친구가 아닌 친구의 친구들과 그의 친구들을 대조해 겹지인이 한명이라도 있으면 그 친구도 그의 2-친구다.

 

겹지인이 한명이라도 있다는 것을 AND 연산으로 처리하고 싶어서,

입력받을 때 Y를 1로 N을 0으로 입력받았다.

 

 

 

따라서 다음과 같이 풀고자 했다.

i번째 행 사람의 2-친구수는
자기 행의 1의 수를 다 더해 2-친구수에 합해 두고(직계 친구 수),
자기행에서 0(N)인 번째를 j라고 하면

j행의 친구와 자기행을 AND 연산하여 그 총합이 1이상이면 (겹지인이 있는 거니까) 자기 2-친구수에 1을 더한다.

 

 

코드는 아래와 같이 작성했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    cin.ignore();

    vector<string> arr;
    string arr2;

    for (int i = 0; i < N; i++) {
        cin >> arr2;
        for (int j = 0; j < N; j++) {
            if (arr2[j] == 'Y') {
                arr2[j] = 1;
            } else if (arr2[j] == 'N') {
                arr2[j] = 0;
            }
        }
        arr.push_back(arr2);
    }

    /*i번째 사람의 친구수를 구해서 친구수 벡터에 넣기*/

    vector<int> friends;

    for (int i=0; i<N ; i++){
        int sum = 0;
        sum = accumulate(arr[i].begin(), arr[i].end(), 0); // 자신의 직계 친구 수의 합

        /*직계 친구는 아니지만 겹지인이 있는 경우 체크*/
        for (int j=0; j<N; j++){
            if ((arr[i][j]==0)&(i!=j)){
                vector<int> result(N);

                /*AND 연산한 배열이 겹지인의 수니까 겹지인이 1명이라도 있으면 2-친구로 세어야 함*/
                transform(arr[i].begin(), arr[i].end(), arr[j].begin(), result.begin(), [](int a, int b) { return a & b; });
                if(accumulate(result.begin(), result.end(), 0) != 0) { sum += 1; }
            }
        }
        friends.push_back(sum);
    }

    sort(friends.rbegin(),friends.rend());
    cout << friends[0] << endl ;
}

코드에서

 

transform(arr[i].begin(), arr[i].end(), arr[j].begin(), result.begin(), [](int a, int b) { return a & b; });

 

이 부분을 살펴보면

 

arr[i]의 begin부터 end까지를, arr[j]의 begin부터와 AND연산해서(얘는 끝을 표시하지 않아도 된다.),

result의 begin부터 저장한다는 뜻이다.

이때 AND연산에 해당하는 내용이 뒤의 [](int a, int b) { return a & b; }이다.

이것은 람다 함수로 transform 함수의 이항 연산자로 사용된다.

이 람다 함수는 두 개의 정수 a와 b를 인자로 받아서 논리 AND(비트 AND) 연산인 a & b의 결과를 반환한다.

 

엄청 간단하게 짠 사람들도 많은 것 같다..

그리고 파이썬으로 하면 더 간단했을 듯.