[백트래킹] 스타트와 링크 (백준 14889번)

#include <iostream>
using namespace std;
 
int startLink[21];
int arr[21][21];
int visited[21];
int n;
 
void dfs(int cnt, int start)
{
    if (cnt == n / 2)
    {
        for (int i = 0; i < n / 2; i++)
                cout << startLink[i] << ' ';
        cout << endl;
        return;
    }
 
    for (int i = start + 1; i <= n; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            startLink[cnt] = i;
            dfs(cnt + 1, i);
            visited[i] = false;
        }
    }
}
 
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> arr[i][j];
 
    dfs(0, 0);
}

내용이 길어서 잘리긴 했지만, 만약 n = 8인 형태의 arr를 입력하게 된다면,

중복이 없는 오름차순으로 1 2 3 4 부터 5 6 7 8 까지 출력한다.

이렇게 만든 이유는, 만약 n/2 (이 경우에는 4)의 값만큼 startTeam에 넣을 수 있다면,

나머지는 자동으로 linkTeam이 될 것이기 때문이다.

 

아래는 위의 dfs 함수를 수정하여 만든 정답이다.

 

#include <iostream>
using namespace std;
 
int startLink[21];
int arr[21][21];
int visited[21];
int n;
 
int minV = 987654321;
 
void dfs(int cnt, int start)
{
 
    if (cnt == n /2 )
    { 
        int sumA = 0, sumB = 0;
        for (int i = 0; i < n / 2; i++)
        {
            for (int j = i + 1; j < n / 2; j++)
            {
                sumA += (arr[startLink[i]][startLink[j]] + arr[startLink[j]][startLink[i]]);
            }
        }
        // sumA는 start팀의 점수를 구하는 것.
 
        int link[21];
        // link 팀의 점수를 구하기 위해서 link팀 배열을 만들고, start 팀에 없는 사람을 넣는다.
        // 아래의 반복문이 cnt가 n/2인 시점에서 방문하지 않은 곳들을 찾아 배열에 대입해준다.
        int cur = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i])
                link[cur++] = i;
        }
 
        for (int i = 0; i < n / 2; i++)
        {
            for (int j = i + 1; j < n / 2; j++)
            {
                sumB += (arr[link[i]][link[j]] + arr[link[j]][link[i]]);
            }
        }
        // 마찬가지로 sumB는 link팀의 점수를 구하는 것.
        if (minV > abs(sumA - sumB)) minV = abs(sumA - sumB);
        // if (minV == 0) { cout << 0; return 0;} 로 끝내버려도 된다.
        return;
    }
 
    for (int i = start + 1; i <= n; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            startLink[cnt] = i;
            dfs(cnt + 1, i);
            visited[i] = false;
        }
    }
    // 전형적인 n과 m 코드다.
    // dfs의 매개변수로는 현재 start팀에 입력된 멤버의 숫자와 탐색 시작점이다.
    // dfs의 두번째 매개변수로 i를 넣은 것을 볼 수 있을 텐데,
    // 이 두번째 매개변수 덕분에 오름차순으로 삽입이 진행된다.
}
 
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> arr[i][j];
 
    dfs(0, 0);
 
    cout << minV;
}

 

느낀점

 

풀다가 죽을 뻔 했는데, n과 m 문제가 생각난 것이 신의 한수였다.

dfs임에도 계속 중복이 나왔던 이유를 다음과 같이 생각해볼 수 있겠다.

 

1) dfs를 2갈래 나눠서 start팀에 대입한 경우와 link팀에 대입한 경우를 구한 것, 결국 분화된다.

2) 시작점을 따로 명시하지 않은 점. (1 2 3 4를 7~8번 정도 하여 시간초과 발생.)

 

해결책은 dfs식을 하나로 통합하고, 탐색 시작 지점을 dfs의 두번째 매개변수로 전달한 것.

신의 한수였다고 잘도 말했지만, 정말로 머리에 한계가 왔다.

지금의 이 짜릿함이 없다면, 내일 아마 코딩에 손도 못댔을 것이다.

문제를 풀고자 지금까지 매달린 게 다행이다, 코딩에 정 떨어지기 전에 오늘은 빨리 관두자.