[BOJ알고리즘, C++]#14889_스타트와 링크, DFS, 깊이 우선 탐색

 

[BOJ 알고리즘, C++] #14889_스타트와 링크, DFS, 깊이 우선 탐색

 

BOJ 알고리즘 문제 풀이, 14889_스타트와 링크

깊이 우선 탐색을 통해 차이 값이 최소가 되는 두 배열을 구합니다.

 

---

 

문제

 

풀이

1. 깊이 우선 탐색 알고리즘 활용

[BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색

 

2. 풀이

1. 깊이 우선 탐색을 통해 각 정점(각 선수)을 방문합니다.
2. 더불어, 루트 노드를 시작으로 인접 노드들을 순차적으로 순회하지 않고, 각 정점들을 모두 루트 노드로 설정하고 깊이 우선 탐색을 진행합니다.
3. 최대 방문 정점 개수를 "N/2"으로 제한합니다. (나머지 정점을 상대 팀으로 설정합니다)
4.  "Count"가 "N/2"에 도달하면, 방문한 정점들을 한 팀으로 설정하고, 방문하지 않은 정점들을 다른 팀으로 설정합니다.
5. 두 배열의 합산 점수를 비교하며, 최소 차이 값을 내는 두 배열을 찾아서 결과 값을 출력합니다.

 

예제 코드

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

bool team[20] = {};
int score[20][20] = {};
int N, mymin = 99999999;
void teamset(int idx, int cnt)
{
    vector<int> start; // 스타트 팀원의 인덱스값
    vector<int> link;  // 링크팀 팀원의 인덱스값
    int start_score = 0;
    int link_score = 0;
    if (cnt == (N / 2))
    {
        for (int i = 0; i < N; i++)
        {
            if (team[i] == true) // 선택된 사람들은 start팀에
                start.push_back(i);
            else // 그 외의 사람들은 link팀으로
                link.push_back(i);
        }
        for (int i = 0; i < (N / 2); i++)
            for (int j = 0; j < (N / 2); j++)
            {
                start_score += score[start[i]][start[j]];
                link_score += score[link[i]][link[j]];
            } // 각 팀의 능력치의 합 계산
        if (abs(start_score - link_score) < mymin)
            mymin = abs(start_score - link_score);
        return;
    }
    for (int i = idx; i < N; i++)
    {
        if (team[i])
            continue;
        else
        {
            team[i] = true;
            teamset(i, cnt + 1);
            team[i] = false;
        }
    }
}
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &score[i][j]);
    teamset(0, 0);
    printf("%d", mymin);
}