14889번-스타트와 링크

문제

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

14889번: 스타트와 링크

 

---

접근방법

1) 접근 사고

start팀과 link팀을 구분하기 위해 visited배열을 활용하여 탐색의 높이가 3이 되었을 때 visited 배열값을 활용하여 팀을 구분하고 결과 값을 계산하여 최소값을 갱신해주었습니다.

 

2) 시간 복잡도

BackTracking을 통한 모든 경우를 탐색해야 하므로 O(n^2)의 시간복잡도를 가집니다.

 

3) 배운 점

구현력이 무럭무럭 자라고 있습니다.

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 21;
int n;
int board[MAX][MAX];
bool visited[MAX];
int ret = INT_MAX;
 
int main(void)
{
    fastio;
    cin >> n;
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
        }
    }
 
    auto DFS = [&](int cur, int cnt, auto&& DFS) -> void{
        if(n / 2 == cnt)
        {
            //visited 배열값을 활용하여서 값들을 분류해준다.
            vector<int> startTeam, linkTeam;
            for(int i = 0; i < n; i++)
            {
                if(visited[i])
                    startTeam.push_back(i);
                else
                    linkTeam.push_back(i);
            }
 
            int startRet = 0;
            int linkRet = 0;
            //start팀과 link팀의 수치를 구한뒤에 최소값을 갱신한다.
            for(int i = 0; i < startTeam.size(); i++){
                for(int j = i + 1; j < linkTeam.size(); j++){
                    int start_y = startTeam[i];
                    int start_x = startTeam[j];
                    int link_y = linkTeam[i];
                    int link_x = linkTeam[j];
 
                    startRet += board[start_y][start_x] + board[start_x][start_y];
                    linkRet += board[link_y][link_x] + board[link_x][link_y];
                }
            }
            ret = min(ret, abs(startRet- linkRet));
            return ;
        }
 
        //start팀과 Link팀의 구분을 위해서 체크를 해준다.
        for(int i = cur + 1; i < n; i++){
            visited[i] = true;
            DFS(i, cnt + 1, DFS);
            visited[i] = false;
        }
    };
 
    DFS(0,0, DFS);
    cout << ret << "\n";
}