[삼성SWTest준비]14889번 스타트와 링크

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

삼성SW 기출 문제 한 번에 보기 : https://www.acmicpc.net/workbook/view/1152

 

삼성 SW 역량평가 기출문제 어떻게 풀지?

먼저, 1,2,3팀과 4,5,6팀 생성, 1,2,4팀 3,5,6 팀 이런식으로 팀을 생성하는 과정에서 팀을 나누는 것이 가장 중요하다고 판단을 했습니다.

그래서 경로를 끝까지 탐색할 수 있는 DFS를 사용했습니다.

그리고 N/2의 인원이 모인다면 계산을 통해 차이의 최소를 구하려고 하였습니다. 

하지만 끝까지 경로를 들어갔을 때 다시 뒤로 나와서 다른 팀 구성의 차이를 구해야 하기 때문에 백트래킹을 사용하였습니다.

※필요 역량 정리하기!!!※

1. dfs

2. 백트래킹

백트래킹 연습 URL : https://www.acmicpc.net/workbook/view/344

#include<iostream>
#include<algorithm>
#define INF 100000000
 
using namespace std;
 
int map[21][21];
bool visit[21];
 
int n,result,ans=INF;
 
void dfs(int v, int len);
void calculate();
int sum(int* a);
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }
    dfs(0,0);
 
    printf("%d", ans);
    return 0;
}
 
 
int sum(int a[]) {
    int sum = 0;
    for (int i = 1; i <= n / 2; i++) {
        for (int j = i + 1; j <= n / 2; j++) {
            sum += map[a[i]][a[j]];
            sum += map[a[j]][a[i]];
        }
    }
    return sum;
}
void calculate() {
    int a[11];
    int b[11];
    int ai = 1,bi=1;
    for (int i = 1; i <= n; i++) {
        if (visit[i]) {
            a[ai++] = i;
        }
        else {
            b[bi++] = i;
        }
    }
    int asum = sum(a);
    int bsum = sum(b);
 
    if (asum > bsum)
        result = asum - bsum;
    if (bsum > asum)
        result = bsum - asum;
 
    ans = min(ans, result);
}
void dfs(int v, int len) {
    if (n / 2 == len) {
        calculate();
    }
    else {
        for (int i = v + 1; i <= n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(i, len + 1);
            }
        }
    }
    visit[v] = false; // 백트래킹
}