2020/07/06 공부 - backtracking

 오늘은 backtrack 마지막 문제, 스타트와 링크를 풀었다.

 총 N명의 사람 중 N/2명을 고르는 것이므로 $_nC_{n/2}$ 만큼의 경우의 수를 봐 주어야 한다.

 총 1부터 8까지 사람이 있으면

 1 2 3 4
 1 2 3 5
 1 2 3 6
 1 2 3 7
 1 2 3 8
 1 2 4 5
 1 2 4 6
 1 2 4 7
 ...
 2 3 4 5
 2 3 4 6
 ...

 대충 이런식으로 조합 경우의 수가 정해지기 때문에, 제일 최근에 탐색한 사람 다음 사람부터 DFS를 실행했다.

 그리고 N이 짝수인 것은 보장되었기 때문에 depth가 N/2가 되면 점수 계산을 진행한다. 조금 더 깔끔한 코드도 존재할 수 있겠지만 아직 그 정도의 실력이 안 되는 것 같다.

 전체적인 구조는 다른 backtrack 문제들과 동일하다. depth가 일정 깊이에 도달하면 stop하고 점수를 계산한다. 안 그러면 내가 원하는 DFS를 진행한다. 위에 언급한 것처럼 '조합의 특성'을 코드로 생각하는 게 좀 어려웠다.

 

void DFS(vector<vector<int>>& stat, vector<bool>& people_in_start, int depth, int N, int& stat_difference, int recently_searched_people) {
    if (depth == N / 2) {
        int team_stat_start = 0;
        int team_stat_link = 0;
        vector<int> team_start;
        vector<int> team_link;
        for (int i = 0; i < N; i++) {
            if (people_in_start[i] == true) team_start.push_back(i);
            else team_link.push_back(i);
        }
        for (int i = 0; i < team_start.size(); i++) {
            for (int j = i + 1; j < team_start.size(); j++) {
                team_stat_start += stat[team_start[i]][team_start[j]];
                team_stat_start += stat[team_start[j]][team_start[i]];
            }
        }
        for (int i = 0; i < team_link.size(); i++) {
            for (int j = i + 1; j < team_link.size(); j++) {
                team_stat_link += stat[team_link[i]][team_link[j]];
                team_stat_link += stat[team_link[j]][team_link[i]];
            }
        }
        stat_difference = min(stat_difference, abs(team_stat_link-team_stat_start));
        return;
    }
    else {
        // DFS
        for (int i = recently_searched_people+1; i < N; i++) {
            people_in_start[i] = true;
            DFS(stat, people_in_start, depth + 1, N, stat_difference, i);
            people_in_start[i] = false;
        }
        // 처음에는 1부터 n/2까지, 그다음엔 1부터 n/2-1 + n/2+1, n/2+2, ...
        // 이 문이 생각보다 생각하기 어려웠음. 조합을 떠올리기
    }
}

 

 이제 입력받고 실행 함수를 적으면 끝일 것이다.

 

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> stat(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> stat[i][j];
        }
    }
    int stat_difference = 1000000000;
    vector<bool> people_in_start(N);

    DFS(stat, people_in_start, 0, N, stat_difference, 0);
    cout << stat_difference;
}