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

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

 

앞선 문제

https://lee-soo.tistory.com/27

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

를 꼭 풀고 와주세요

 

여기선 단순히 팀의 인원수가 상관 없다고 되어있네요

그럼 모든 경우의 수를 보면 됩니다

앞서 스타트와 링크문제에서 풀때는 depth==n/2일때밖에 없었죠?

 

하지만 지금은 인원수 상관없이 depth>0 으로 하면 됩니다

왜냐면 1명이상이 되면 상관이 없으니까여

 

대신 return을 없애주어야 합니다.

 

왜냐면 depth가 깊어지지않고 초반에 계속 머무를 수 있기 때문이에요

 

이게 무슨뜻이냐면 depth>0이상일때는 무조건 return이 되니까 아래있는 중복문에서 depth가 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 > 0)

    {

        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));

        }

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

    {

        if (!visited[i])

        {

            visited[i] = true;

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

            visited[i] = false;

        }

    }

}

앞선 문제하고 달라진건 depth>0 조건문과 return이 사라진 것 밖에 없답니다.