[BOJ - 14889] 스타트와 링크 (C++)

문제

접근방법

• 어느 팀으로 선택되는지 백트래킹을 통해서 결정하는 문제로 판단
• 문제에서 주어진 사진을 보면 i, j가 같은 { ex) (1, 1), (2, 2) } 부분을 제외하고 탐색을 하면 된다
  • -> visited 배열을 N으로 설정 후 count가 N/2가 되는 지점에서 서로의 차이를 체크

 

코드

#include <iostream>
#include <vector>

using namespace std;
#define INF 1e9

int N;
vector<vector<int>> S;
vector<int> visited;
int min_diff = INF;

void calculate() {
    int start_sum = 0, link_sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (visited[i] && visited[j])
                start_sum += (S[i][j] + S[j][i]);
            else if (!visited[i] && !visited[j])
                link_sum += (S[i][j] + S[j][i]);
        }
    }

    int diff = (start_sum > link_sum ? start_sum - link_sum : link_sum - start_sum);
    min_diff = min(diff, min_diff);
}

void dfs(int idx, int count) {
    if (count == N/2) {
        calculate();
        return;
    }

    for (int i = idx; i < N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(i+1, count+1);
            visited[i] = false;
        }
    }
}

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

    cin >> N;

    S.assign(N, vector<int>(N));
    visited.assign(N, false);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> S[i][j];
        }
    }

    dfs(0, 0);

    cout << min_diff;

    return 0;
}

링크

14889번: 스타트와 링크