search

jeongabae / Baekjoon_Python

파이썬으로 푼 백준 - 2023.02.05 누적 440문제, 파이썬으로 푼 코드업 - 기초 100제 풀이 완료
0 stars 0 forks source link

[Brute Force][DFS][Backtracking] 백준 14889번 : 스타트와 링크 #301

Closed jeongabae closed 2 years ago

jeongabae commented 2 years ago

실버2

시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 -- | -- | -- | -- | -- | -- 2 초 | 512 MB | 64889 | 32478 | 19017 | 46.803%

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

  • 스타트 팀: S12 + S21 = 1 + 4 = 5
  • 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

  • 스타트 팀: S13 + S31 = 2 + 7 = 9
  • 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입력 1 

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

예제 출력 1 

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 

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

예제 출력 3 

1

힌트

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

출처

알고리즘 분류

제출한 코드 1 : 조합 함수 이용 풀이

from itertools import combinations
import sys
def input():
    return sys.stdin.readline().rstrip()

N = int(input()) #축구를 하기 위해 모인 사람은 총 N명
S = [list(map(int, input().split())) for _ in range(N)] #능력치 행렬
choice = [0]*N #팀 결정 1이면 start팀 0이면 link팀. 
min_diff = sys.maxsize #int의 최대값이 sys.maxsize이므로 이렇게 일단 해둠.

def calculate_diff():
    team_start=0 #start팀의 능력치 합
    team_link=0 #link팀의 능력치 합
    for i in range(N-1):
        for j in range(i+1,N):
            if choice[i] and choice[j]: #만약 i,j번이 1(start팀)이라면
                team_start += S[i][j] + S[j][i]
            elif not choice[i] and not choice[j]:  #만약 i,j번이 0(link팀)이라면
                team_link += S[i][j] + S[j][i]
    return abs(team_start-team_link)

for i in list(combinations(range(0,N), N//2)): #N에서 절반 만큼 start팀을 할 사람을 뽑아서
    choice = [0] * N
    for j in range(len(i)):
        choice[i[j]] = 1 #start팀이라고 표시해준다.

    min_diff = min(min_diff, calculate_diff()) #뽑았으니 뭐가 더 작은지 비교 후 대입

print(min_diff)

제출한 풀이2 : 백트래킹 이용. 이 풀이는 풀이1인 조합 이용 풀이보다 시간은 더 느리지만 메모리 더 적게 씀

import sys
def input():
    return sys.stdin.readline().rstrip()

N = int(input()) #축구를 하기 위해 모인 사람은 총 N명
S = [list(map(int, input().split())) for _ in range(N)] #능력치 행렬
choice = [0]*N #팀 결정 1이면 start팀 0이면 link팀. 
min_diff = sys.maxsize #int의 최대값이 sys.maxsize이므로 이렇게 일단 해둠.

def calculate_diff():
    team_start=0 #start팀의 능력치 합
    team_link=0 #link팀의 능력치 합
    for i in range(N-1):
        for j in range(i+1,N):
            if choice[i] and choice[j]: #만약 i,j번이 1(start팀)이라면
                team_start += S[i][j] + S[j][i]
            elif not choice[i] and not choice[j]:  #만약 i,j번이 0(link팀)이라면
                team_link += S[i][j] + S[j][i]
    return abs(team_start-team_link)

def dfs(start):
    global min_diff
    if choice.count(1) == N // 2:  # start팀에 N의 절반만큼 사람이 왔다면!
        min_diff = min(min_diff, calculate_diff()) #뭐가 더 적은지 선택 후 대입
        return

    for i in range(start, N): #start~N
        if not choice[i]: #start팀이 아니라면
            choice[i] = 1 #start팀으로
            dfs(i+1) #start는 지금까지 수열에 있는 수보다 커야하므로 1더해준다.
            choice[i] = 0

dfs(0)
print(min_diff)