백준 3980번 : 선발 명단

  비트마스크를 공부해볼까 하고 풀어본 문제인데 비트마스크가 뭔지는 모르고 결국 DFS로 푼 문제다... 흠... 풀이 방법은 보통 DFS랑 동일하다.  

s[i][j]	i번째 선수가 j라는 포지션에서의 점수
visited[j]	j번째 포지션이 이미 점유되었는지
dfs(index, score)	현재 index 번호의 선수를 탐색하려 하고 있고 그 전까지 저장된 점수는 score이다.
dfs 종료 조건 index == 11	선수 번호가 0번부터 10번까지이므로 11번이면 점수를 저장하고 종료

  pos자리에 현재 탐색하고 있는 index번의 선수를 채용할 수도 있고 아닐수도 있으므로 두 경우를 모두 탐색해주어야 한다. visited[pos] = true;와 dfs(index + 1, score + s[index][pos])를 한다는 것은 index번의 선수를 pos자리에 채용한다는 뜻이고 visited[pos] = false는 그 선수를 채용하지 않고 넘어간다는 뜻이다.

#include <iostream>

using namespace std;

int n;
int s[11][11];
bool visited[11];
int ans;

void dfs(int index, int score)
{
    if(index == 11)
    {
        ans = max(ans, score);
        return;
    }
    
    for(int pos = 0; pos < 11; pos++)
    {
        if(visited[pos] || s[index][pos] == 0) continue;
        visited[pos] = true;
        dfs(index + 1, score + s[index][pos]);
        visited[pos] = false;
    }
}

void solve()
{
    ans = 0;
    
    for(int i = 0; i < 11; i++)
    {
        for(int j = 0; j < 11; j++)
        {
            cin >> s[i][j];
        }
    }
    
    dfs(0, 0);
    cout << ans << "\n";
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        solve();
    }
 
    return 0;
}