백준 14889 스타트와 링크 C++

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

14889번: 스타트와 링크

최종 코드

• GitHub https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14889.cpp

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ14889
//
//  Created by Hwayeon on 2021/07/07.
//

#include <iostream>
#include <cmath>
using namespace std;

int N;
int S[20][20] = {0, };
int visit[20] = {0,};
int answer = 987654321;

void dfs(int idx, int start_n){
    if(idx >= N) return;
    if(start_n == N/2){
        //능력치 구하기 -> O(n^2)
        int start_sum = 0;
        int link_sum = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
            	//스타트 팀원은 visit[idx] = 1이므로, i,j가 모두 스타트 팀원이면 visit[i]+visit[j] = 2이다.
                if(visit[i]+visit[j]==2) start_sum += S[i][j];
                
                //링크 팀원은 visit[idx] = 0이므로, i,j가 모두 링크 팀원이면  visit[i]+visit[j] = 0이다.
                //i=j인 경우, S[i][j] = 0이므로, 더해줘도 무관하다.
                else if(visit[i]+visit[j]==0) link_sum += S[i][j];
            }
        }
        int differ = abs(start_sum-link_sum);
        //능력치 차가 answer보다 작은 경우, answer 값을 갱신해준다.
        if(differ < answer) answer = differ;
        return;
    }
    
    //스타트 팀원 뽑기 -> 조합 O(2^n)
    for(int i=idx; i<N; i++){
        if(start_n+1<=N/2){
            visit[i] = 1;
            dfs(i+1, start_n+1);
            visit[i] = 0;
        }
    }
}
    
int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> S[i][j];
        }
    }
    dfs(0, 0);
    cout << answer << endl;
    return 0;
}
#시간복잡도 = O(2^n*n^2) 공간복잡도 = O(n)

---

최종 풀이

풀이 시간 1시간 1분

//
//  main.cpp
//  BJ14889
//
//  Created by Hwayeon on 2021/07/07.
//

#include <iostream>
#include <cmath>
using namespace std;

int N;
int S[20][20] = {0, };
int visit[20] = {0,};
int answer = 987654321;

void dfs(int idx, int start_n){
    if(idx >= N) return;
    //팀 배정 완료
    if(start_n == N/2){
        //능력치 구하기
        int start_sum = 0;
        int link_sum = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visit[i]+visit[j]==2) start_sum += S[i][j];
                else if(visit[i]+visit[j]==0) link_sum += S[i][j];
            }
        }
        int differ = abs(start_sum-link_sum);
        if(differ < answer) answer = differ;
        return;
    }
    
    //팀원 뽑기
    for(int i=idx; i<N; i++){
        if(start_n+1<=N/2){
            visit[i] = 1;
            dfs(i+1, start_n+1);
            visit[i] = 0;
        }
    }
}
    
int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> S[i][j];
        }
    }
    dfs(0, 0);
    cout << answer << endl;
    return 0;
}

 

---

이전 풀이

풀이 시간  1시간 6분

//
//  main.cpp
//  BJ14889
//
//  Created by Hwayeon on 2021/01/06.
//

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N, start_s, link_s;
vector<vector<int> > s;
int min_ds = 987654321;
vector<int> start_team, link_team;
bool visit[20] = {false,};

void get_ds(){
    link_team.clear();
    start_s = 0;
    link_s = 0;
    for(int i=0; i<N; i++){
        if(!visit[i]) link_team.push_back(i);
    }
    for(int i=0; i<N/2; i++){
        for(int j=0; j<N/2; j++){
            start_s += s[start_team[i]][start_team[j]];
            link_s += s[link_team[i]][link_team[j]];
        }
    }
    if(abs(start_s-link_s) < min_ds) min_ds = abs(start_s-link_s);
}

void make_start_team(int idx){
    if(start_team.size() == N/2) {
        get_ds();
        return;
    }
    int n;
    for(n=idx; n<N; n++){
        if(visit[n]) continue;
        visit[n] = true;
        start_team.push_back(n);
        make_start_team(n);
        visit[n] = false;
        start_team.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    vector<int> row;
    for(int i=0; i<N; i++){
        row.clear();
        for(int j=0; j<N; j++){
            int s_num;
            cin >> s_num;
            row.push_back(s_num);
        }
        s.push_back(row);
    }
    make_start_team(0);
    cout << min_ds << endl;

    return 0;
}

 

1. 완전 탐색 > DFS

먼저, start_team과 link_team 각각 N/2명의 팀원을 구성해야 한다.

나는 start_team을 먼저 구성하고, 나머지 팀원을 link_team에 배정했다. (문제에서 N은 항상 짝수로 주어진다.)

 팀을 구성하는 방법은 DFS를 활용했다.

새 팀원을 뽑으면, 이를 구분하기 위해 visit[n] = true로 해주고 재귀를 통해 start_team이 N/2가 될 때까지 팀원을 뽑아준다.

재귀 이후에 또 다른 조합을 만들기 위해 visit[n] = false와 start_team/pop_back() 하여 뽑은 팀원을 다시 빼주도록 한다.

 start_team 구성이 끝나면 link_team을 구성하고 팀 능력치 차이를 계산하는 get_ds() 함수로 넘어가며 탐색을 종료한다.

 

 

 

 

 

 

2. 팀 능력치 계산

 팀 능력치를 계산할 때의 포인트는 문제에서 주어지는 행렬이 S(i,i)인 경우에는 0 이라는 것이다.

따라서, 2중 for문을 사용하여 더한 후에 abs를 이용하여 start_s와 link_s 값의 차이를 계산할 수 있다.

 

 

---

참고

• 2021/01/11 - [C++] - [알고리즘] BFS와 DFS

[알고리즘] BFS와 DFS