[BOJ] 3980 - 선발 명단

💎 문제

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.

오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다.

수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.

이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

💎 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100사이의 11개의 정수 sij를 포함하고 있다. sij는 i번선수가 j번 포지션에서 뛸 때의 능력이다. 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)

💎 출력

각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.

💎 풀이 방법

정말 오랜만에 백트래킹 문제이다! 문제에서 주어진 범위에 크기 또한 11로 시간초과가 날 염려는 적을 것으로 예상되어 맘 편하게 풀 수 있었던 문제였다. 또한 문제에서 주어진 선수를 선택하는 조건만 잘 생각한다면 손쉽게 풀 수 있던 문제였다!!

백트래킹은 설정한 깊이에 도달하였을 때의 값이 내가 기대한 값일 경우에 저장해준 뒤 반환해주면 된다!! 따라서 설정한 깊이에 도달할 때까지 선수를 한명씩 선발하고 그들의 능력치 합들을 더한 것과 다른 값들을 비교해주면서 최댓값을 출력해준다!!

나는 이 문제에서는 11명의 선수의 11개의 포지션에서의 능력치들을 저장하는 squad 배열과 함께 11개의 포지션에 선수가 선정되었는지 확인하는 bool 변수를 이용하였다. 이 둘을 이용해서 만약 포지션에 선수가 선정되지 않았을 경우에만 재귀함수를 실행할 것이다!!

void backtracking(int dept, int ability){
    
    if(dept == 11){
        if(ability >= result)
            result = ability;
        return;
    }
    
    vector <pair<int, int>> maxPosition;
    for(int i = 0;i < 11;i++){
        if(squad[dept][i] != 0)
            maxPosition.push_back({squad[dept][i], i});
    }
    
    sort(maxPosition.begin(), maxPosition.end());
    
    for(int i = 0;i < maxPosition.size();i++){
        if(!check[maxPosition[i].second]){
            check[maxPosition[i].second] = true;
            backtracking(dept + 1, ability + maxPosition[i].first);
            check[maxPosition[i].second] = false;
        }
    }
}

백트래킹 함수를 확인해보면 현재 도달한 깊이와 능력치의 합을 저장하는 변수 두 개를 매개변수로 한다. 앞서 말했듯이 깊이가 11에 도달하면 포지션에 모두 선수가 위치해 있으므로 지금까지 더한 능력치의 합이 결과로 출력할 값보다 크다면 그것을 결과값으로 저장해주고 반환해주면 된다!!

여기서 중요한 것은 어떻게 각 선수들이 최대인 능력치들로만 포지션에 선정할지 인데, 이때 나는 먼저 해당 포지션에 11명의 선수들이 위치하였을 때 0인 능력치들을 제외한 나머지들을 벡터를 이용하여 저장해주었다. 이 벡터에는 능력치와 함께 그 포지션의 자리를 뜻하는 index까지 pair을 이용하여 저장해준다. 따라서 이를 정렬해준다면 가장 최대인 능력치부터 선수들의 포지션을 정해주고 만약 불가하다면 되돌아가서 다음으로 최대인 능력치의 포지션을 정해줄 수 있을 것이다!

그래서 앞에서 정렬한 pair vector를 이용하여 선수의 최대가 되는 능력치의 포지션이 비어있다면(pair vector에 저장한 index를 이용)그 포지션을 설정하였다면 bool변수를 바꿔주고 재귀함수를 통해 다음 깊이의 포지션에 해당하는 선수를 찾아준다!!

위 내용대로 두 가지 조건 첫째로 어떤 식으로 해당 포지션에 최대인 능력치의 선수를 찾아낼지, 포지션에 선수를 배정했다면 다시 고르지 않도록 어떻게 해야할지 고려한다면 쉽게 풀 수 있는 문제였다!!

💎 전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int T;
int squad[11][11];
bool check[11];
int result = 0;

void backtracking(int dept, int ability){
    
    if(dept == 11){
        if(ability >= result)
            result = ability;
        return;
    }
    
    vector <pair<int, int>> maxPosition;
    for(int i = 0;i < 11;i++){
        if(squad[dept][i] != 0)
            maxPosition.push_back({squad[dept][i], i});
    }
    
    sort(maxPosition.begin(), maxPosition.end());
    
    for(int i = 0;i < maxPosition.size();i++){
        if(!check[maxPosition[i].second]){
            check[maxPosition[i].second] = true;
            backtracking(dept + 1, ability + maxPosition[i].first);
            check[maxPosition[i].second] = false;
        }
    }
}

int main(int argc, const char * argv[]) {

    cin >> T;
    while(T--){
        for(int i = 0;i < 11;i++){
            for(int j = 0;j < 11;j++){
                cin >> squad[i][j];
            }
        }
        backtracking(0, 0);
        cout << result << "\n";
        result = 0;
        for(int i = 0;i < 11;i++){
            check[i] = false;
        }
    }
    return 0;
}

💎 고민

오랜만에 알고리즘 문제를 해결하고 velog에 게시해본다,,!! 개강하면서 알고리즘을 자주 푸는데에 어려움이 있지만,,,시간나는대로 꼭 풀어서 감을 잃지 않도록하자!! 그리고 이렇게 정리하는 습관이 정말 나에게 도움되는 것 같아서 잘 풀어보고 이렇게 velog에 게시하도록 해보자!!
개강하면서 차근차근 하다보니 하나둘씩 일들이 잘 풀려가고 있는 것 같다. 계획대로 실행하고 그것들을 실천하다보니 성취감이 배로 다가오는 것 같다!! 더 열심히하자 성공하장

화팅!!