백준 3980 선발 명단 C++

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

3980번: 선발 명단

---

문제

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

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

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

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

---

입력

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

---

출력

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

---

처음에 next_permutation으로 순열을 만들어서 풀었는데 시간초과 나서, 다른 분들의 코드를 참고하여서 풀었습니다.

 

일단, 1번부터 11번까지의 선발 선수가 있습니다. 그리고 각 선수마다 포지션별로 능력이 있는데, 포지션의 능력이 0이면,

해당 자리에서 뛸 수 없습니다.

 

모든 포지션을 선발 선수로 채웠을 때, 포지션의 능력치의 합의 최대값을 구하는 것이 목적입니다.

일단 선발선수가 1번부터 ~ 11번까지 있고, 포지션도 11개 존재합니다.

 

그래서, 1번부터 11번까지 선수들에 대해서 11개의 포지션 각각에 대해서 백트래킹을 진행합니다.

 

ex)

1번선수-1번포지션

1번선수-2번포지션,,,,

1번선수-11번 포지션...

 

 

2번선수-1번포지션...

....

 

이 과정에서, 선수가 해당 포지션의 능력이 0이면 백트래킹을 하지 않습니다.

일단 2차원 배열 map[i][j]는 i번선수가 j번 포지션에서 뛸 떄의 능력치를 나타냅니다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[11];
int arr[11][11];

vector<int> player;
int max_ = -1;

void dfs(int start,int sum){
    if(start == 11){
        if(max_ < sum){ //포지션의 합의 최대값이 기존 값보다 크다면 갱신하는 코드
            max_ = sum;
        }
        return;
    }
    for(int i = 0;i<11;i++){ //start번째 선수에 대해서 1번~11번까지 포지션에 대해서 백트래킹
        
        if(visited[i] == false && arr[start][i] != 0){ 
            //배열 [선수][포지션]의 값이 0이 아니면(해당 선수가 해당 포지션에서 뛸때의 능력이 0이 아니면)
            //백트래킹 실행
            
            visited[i] = true;
            dfs(start+1,sum+arr[start][i]);
            visited[i] = false;
        }
    }
}


int main(void){
    int t;
    cin >> t;
    while(t--){
        player.clear();
        for(int i = 0;i<11;i++){
            visited[i] = false;
        }
        max_= -1;
        
        for(int i = 0;i<11;i++){
            for(int j = 0;j<11;j++){
                cin >> arr[i][j];
            }
            player.push_back(i);
        }
        
        dfs(0,0);
        cout << max_ << '\n';
    }
  
    
}