백준 14889 : 스타트와 링크

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

14889번: 스타트와 링크

 

#include <iostream>
 
int n, ans = 987654321;
int team[21][21];
bool visited[21];
 
void input()
{
    std::cin >> n;
    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < n; ++x)
        {
            std::cin >> team[y][x];
        }
    }
}
 
int chk(bool flag)
{
    int rest = 0;
    for (int y = 0; y < n; ++y)
    {
        if (visited[y] == flag)
        {
            for (int x = y; x < n; ++x)
            {
                if (visited[x] == flag)
                {
                    rest += team[y][x] + team[x][y];
                }
            }
        }
    }
    return rest;
}
// 0 3 4
// 2 0 4
// 2 4 0
// 19
// 0 2 5
// 1 0 5
// 1 3 0
// 17
void solve(int stk, int fSum, int pivot)
{
    if (stk == n / 2)
    {
        int temp = chk(false);
        int cmpTemp = abs(temp - fSum);
 
        if (cmpTemp < ans)
        {
            ans = cmpTemp;
        }
        return;
    }
 
    for (int i = pivot; i < n; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            int temp = 0;
            for (int j = 0; j < i; ++j)
            {
                if (visited[j])
                {
                    temp += team[i][j] + team[j][i];
                }
            }
            solve(stk + 1, fSum + temp, i);
            visited[i] = false;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve(0, 0, 0);
    output();
    return 0;
}

 

완전탐색이지만, 중복에 대한 검사를 어느정도는 해 줘야 풀린다.

 

사실 fSum이 크게 필요는 없었던 것이 아닐까?

 

int chk(bool flag)
{
    int rest = 0;
    for (int y = 0; y < n; ++y)
    {
        if (visited[y] == flag)
        {
            for (int x = y; x < n; ++x)
            {
                if (visited[x] == flag)
                {
                    rest += team[y][x] + team[x][y];
                }
            }
        }
    }
    return rest;
}
 
void solve(int stk, int fSum, int pivot)
{
    if (stk == n / 2)
    {
        int temp = chk(false);
        int fff = chk(true);            //변경!
        int cmpTemp = abs(temp - fff);    //변경!
 
        if (cmpTemp < ans)
        {
            ans = cmpTemp;
        }
        return;
    }
 
    for (int i = pivot; i < n; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            /*int temp = 0;
            for (int j = 0; j < i; ++j)
            {
                if (visited[j])
                {
                    temp += team[i][j] + team[j][i];
                }
            }*/
            solve(stk + 1, fSum, i);
            visited[i] = false;
        }
    }
}

그것은 팩트였구요

 

하지만 기존에 비해 좀 더 느리다.

 

중요한 점은 dfs 탐색 시 중복값을 얼마나 잘 걸러내느냐

 

모든 배열에 대해 탐색할 필요는 없다

 

이렇게만 탐색해도 충분하다