[BJ14889] 스타트와 링크

🚩 문제 설명

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

14889번: 스타트와 링크

⏱️ 시간 복잡도
▪log(N) x N^2

◾ 짝수의 사람을 두개의 팀으로 나눕니다.

◾ 사람마다 각각 팀원들마다 같은 팀이 되었을 때 시너지 능력치가 있습니다.

◾ 두 팀의 능력치를 구하고, 차가 제일 작은 값을 구하는 문제입니다.

 

 

 

---

 

 

 

✅ 입출력

n : 총 사람의 수 (짝수)
s(1) ~ s(n) : n개의 줄, n개의 수
return 스타트 팀과 링크 팀의 능력치 차이의 최솟값

✔️ 예제 1

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

0

✔️ 예제 2

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

2

✔️ 예제 3

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

1

 

 

 

---

 

 

시간초과 코드

import sys

sys.stdin = open('input2.txt', 'rt')
input = sys.stdin.readline
n = int(input())  # 사람의 총수
s = [list(map(int, input().split())) for _ in range(n)]  # 능력치맵

team = [0] * n
visited = []


# 능력치 계산하기
def check_ability():
    global ans
    sum1, sum2 = 0, 0

    ones = [i for i in range(n) if team[i]]
    zeros = [i for i in range(n) if not team[i]]

    if ones in visited or zeros in visited:
        return -2147000, 2147000

    visited.append(ones)
    visited.append(zeros)

    # 스타트팀
    for i in range(n // 2):
        for j in range(i + 1, n // 2):
            sum1 += (s[ones[i]][ones[j]] + s[ones[j]][ones[i]])

    # 링크팀
    for i in range(n // 2):
        for j in range(i + 1, n // 2):
            sum2 += (s[zeros[i]][zeros[j]] + s[zeros[j]][zeros[i]])

    return sum1, sum2


# 백트랙킹
def dfs(cnt):
    global ans

    # 반으로 팀이 구성되어졌다면
    if cnt == n // 2:
        sum1, sum2 = check_ability()
        ans = min(ans, abs(sum1 - sum2))
        return

    for i in range(n):
        if team[i]:  # 팀을 구성했다면
            continue

        team[i] = 1  # 팀구성 처리
        dfs(cnt + 1)  # cnt: 팀 구성원 명수
        team[i] = 0  # 벡트랙킹


if __name__ == '__main__':
    ans = 2147000000
    dfs(0)
    print(ans)

📑 문제 풀이

with 파이썬 (Python) 2시간

import sys

sys.stdin = open('input2.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # 사람의 총수
visited = [0] * n  # 1, 0 으로 팀을 나눈다.
s = [list(map(int, input().split())) for _ in range(n)]  # 능력치맵


def dfs(depth, idx):
    global ans

    # 만약 사람이 두 팀으로 나눠졌다면
    if depth == n // 2:
        sum1, sum2 = 0, 0

        # 브루트포스: 전부를 확인한다
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:  # 0
                    sum1 += s[i][j]
                elif not visited[i] and not visited[j]:  # 1
                    sum2 += s[i][j]

        # 최솟값을 구한다
        ans = min(ans, abs(sum1 - sum2))
        return

    # 백트랙킹
    # idx를 둬서 시간을 줄인다.
    for i in range(idx, n):
        if not visited[i]:
            visited[i] = 1  # 방문 처리
            dfs(depth + 1, i + 1)
            visited[i] = 0  # 백트랙킹


if __name__ == '__main__':
    ans = 2147000000
    dfs(0, 0)
    print(ans)

💬 Point

➡️  DFS() 사용
➡️  브루트포스를 이용하여 꾸려진 팀원 각각을 비교하여 돈다.

◾ pypy3 로 제출해야 시간초과가 나지 않고 정답으로 나옵니다.

◾ 쉽게 합을 풀 수 있는 문제였는데 왜 이렇게 어렵게 생각했을까요

 

input = sys.stdin.readline

n = int(input())  # 사람의 총수
visited = [0] * n  # 1, 0 으로 팀을 나눈다.
s = [list(map(int, input().split())) for _ in range(n)]  # 능력치맵

◾ 입력을 받습니다.

 

# 백트랙킹
# idx를 둬서 시간을 줄인다.
for i in range(idx, n):
    if not visited[i]:
        visited[i] = 1  # 방문 처리
        dfs(depth + 1, i + 1)
        visited[i] = 0  # 백트랙킹

◾ 우선, 백트랙킹을 셀 for 문을 만들어줍니다.

idx 를 이용해서 시간을 줄여줄 수 있습니다. 만약 방문을 했다면 넘겨지고, 방문을 하지 않았다면 방문 처리를 해줍니다.

그리고 다음 depth 로 넘어갑니다. depth 는 한팀에 꾸려지는 사람 수를 이릅니다.

만약 return 이 되면 방문 처리를 한 것을 다시 0으로 만듭니다. 백트랙킹을 합니다.

 

# 만약 사람이 두 팀으로 나눠졌다면
if depth == n // 2:
    sum1, sum2 = 0, 0

    # 브루트포스: 전부를 확인한다
    for i in range(n):
        for j in range(n):
            if visited[i] and visited[j]:  # 0
                sum1 += s[i][j]
            elif not visited[i] and not visited[j]:  # 1
                sum2 += s[i][j]

    # 최솟값을 구한다
    ans = min(ans, abs(sum1 - sum2))
    return

◾ 만약 팀이 두개로 나눠진다면, 브루트포스를 돌아 어느 사람이 1이고 0 인지 확인을 합니다.

해당 두 개의 for문은 (0, 0), (0, 1), (0, 2) .. 이런 식으로 주어진 인덱스의 숫자를 하나하나 다 돕니다.

하나하나 다 돌아서 만약 둘 다 visited 되어 있다면 능력치를 더하게 됩니다.

그러면 스타트팀이 구해지고, 방문처리가 되지 않은 값들은 자연스럽게 다른 팀이 되어 링크팀의 능력치 총합이 됩니다.

그리고나서 min() 을 통해서 최솟값을 구합니다.

abs() 를 이용하여 절댓값을 구하여 비교를 해야합니다. 그리고 재귀에서 빠져나올 수 있도록 return 을 해줍니다.

 

if __name__ == '__main__':
    ans = 2147000000
    dfs(0, 0)
    print(ans)

◾ 메인 함수 입니다. 

 

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 스타트와링크 dfs python 파이썬

# 알고리즘 백준 스타트와 링크 python dfs 파이썬

---