[C++] 백준 14889 스타트와 링크

#include <vector>
#include <iostream>

using namespace std;

int N = 0;
int result = 1001;
vector<bool> visited;
vector<vector<int>> team;

void DFS(int count, int num)
{
    if (count == N / 2)
    {
        int start = 0;
        int link = 0;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (visited[i] && visited[j])
                {
                    start += team[i][j];
                }
                if (!visited[i] && !visited[j])
                {
                    link += team[i][j];
                }
            }
        }

        result = min(result, abs(start - link));

        return;
    }

    for (int i = num; i < N; i++)
    {
        visited[i] = true;
        DFS(count + 1, i + 1);
        visited[i] = false;
    }
}

int main()
{
    cin >> N;

    team = vector<vector<int>>(N, vector<int>(N, 0));
    visited = vector<bool>(N, false);

    //입력
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> team[i][j];
        }
    }

    DFS(0, 0);

    cout << result;

    return 0;
}

 

풀이

1. DFS로 경우의 수들을 탐색한다.

2. 반이 차게 되면 다른 반대편을 알 수 있기에 스코어합산의 차를 계산해준다.

 

느낀점

해당 풀이에는 아쉬운 점이 있는 것 같다. 스코어합산을 미리 계산하거나 더 좋은 중복제거 방법이 있을 것같다.

 

 

 

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