[DFS] 백준 14889번 스타트와 링크(C++)

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

 

풀다 현타옴

어려워서

 

아

 

핵심

 

더블 중복문 안에서, 한번 정해지면 다른팀은 자동으로 정해짐을 알고 있어야함

 

 

사실 이제, 비스무리하게 모든 경우의수를 처리해야 한다는것은 깨닫고 있었고

 

visited를 1차원 배열로 사용해야 함을 깨닫고 있었음

왜?

 

visited[][]을 2차원 배열로 하게되면

1,3의 이 true가 되면 1 4는 false까 1이 또 선택될 수 있는 느낌

 

그래서 단순한 1차원 배열로 사용해야 했어

 

 

 

코드로보여줌

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

bool visited[20];

int arr[20][20];

int sum = 0;

int temp_min = 1000000;

void task(int depth, int n, int id);

int main()

{

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            cin >> arr[i][j];

        }

    }

    task(0, n, 0);

    cout << temp_min << "\n";

}

void task(int depth, int n, int id)

{

    if (depth == n / 2)

    {

        int start = 0, link = 0;

        for (int i = 0; i < n - 1; i++)

        {

            for (int j = i + 1; j < n; j++)

            {

                if (visited[i] && visited[j])

                {

                    start += arr[i][j] + arr[j][i];

                }

                else if (!visited[i] && !visited[j])

                {

                    link += arr[i][j] + arr[j][i];

                }

            }

        }

        temp_min = min(temp_min, abs(start - link));

        return;

    }

    for (int i = id; i < n; i++)

    {

        if (!visited[i])

        {

            visited[i] = true;

            task(depth + 1, n, i + 1);

            visited[i] = false;

        }

    }

}

 

사실 여기서 헷갈렸던게

처음 for문을 들어갈 때, 2중 for문을 사용해서 i,j를 통해 미리 한번 start 팀을 잡고 가려 했는데

 

오히려 복잡해지고 차라리 visited 만 가지고 depth의 길이가 충족될 때 위에서 다 계산하는게 나을거라는 결론을 봄

 

하 어려워