20529번: 가장 가까운 세 사람의 심리적 거리

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int Check[100001];
int Comb[3];
int Mini = 2147000000;
vector<string> vecString;

void DFS(int L, int e, int i, int N)
{
    if (L == e)
    {
        int Sum{};

        // 해당 Comb를 가지고 세 사람의 거리를 구한다.
        // Comb[0], Comb[1]
        for (int i = 0; i < 4; ++i)
        {
            int A = Comb[0];
            int B = Comb[1];

            if (vecString[A][i] != vecString[B][i])
            {
                ++Sum;
            }
        }

        // Comb[1], Comb[2]
        for (int i = 0; i < 4; ++i)
        {
            int B = Comb[1];
            int C = Comb[2];

            if (vecString[B][i] != vecString[C][i])
            {
                ++Sum;
            }
        }

        // Comb[0], Comb[2]
        for (int i = 0; i < 4; ++i)
        {
            int A = Comb[0];
            int C = Comb[2];

            if (vecString[A][i] != vecString[C][i])
            {
                ++Sum;
            }
        }

        if (Mini > Sum)
        {
            Mini = Sum;
        }
    }
    else
    {
        for (; i <= N; ++i)
        {
            if (Check[i] == 1) continue;
            else
            {
                Comb[L] = i;
                Check[i] = 1;
                DFS(L + 1, e, i + 1, N);
                Check[i] = 0;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "rt", stdin);

    int T{}, N{};
    cin >> T;
    string Str;

    for (int i = 0; i < T; ++i)
    {
        cin >> N;

        vecString.push_back("");
        
        for (int j = 0; j < N; ++j)
        {
            cin >> Str;
            vecString.push_back(Str);
        }
		
        // MBTI의 종류가 16개이기 때문에 N이 32보다 큰 경우 정답은 반드시 0이다.
        if (N > 32)
        {
            cout << 0 << '\n';
            vecString.clear();
            continue;
        }

        DFS(0, 3, 1, N);
        
        cout << Mini << '\n';
        
        vecString.clear();
        Mini = 2147000000;
    }

    return 0;
}