[Baekjoon Online Judge] 백준 14889번 스타트와 링크(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 14889번 스타트와 링크

(Python)

(글쓴날 : 2020.03.27)

 

---

* Baekjoon Online Judge, 백준 14889번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 14889번 스타트와 링크

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

2) 풀이 과정

축구를 하는 N명의 인원이 주어지고 그중에서 두 팀으로 나누는데, 나눌 때 어떤 두 명이 같은 팀에 속했을 때 더해지는 능력치가 주어진 S를 참고하여 두 팀의 최종 능력치 총합의 차가 제일 작은 값을 구하는 문제입니다.

 

저의 경우, Python으로 문제를 풀었으며 기본적으로 DFS와 백트래킹을 이용해 문제를 해결했습니다.

0부터 N-1까지의 리스트를 생성한 뒤 index를 사람이라 가정하였고, DFS를 이용해 탐색해가며 팀원을 저장하다 인원이 N/2가 되면 백트래킹 하였습니다.

팀에 사람의 순서는 상관이 없기에 조합을 구했고, 해당 팀의 능력치를 구할 때는 문제에서 주어진 S를 보니 순서가 상관이 있어 순열을 구해 문제를 해결했습니다.

 

Python의 경우, itertools 모듈에 조합과 순열을 구해주는 라이브러리가 이미 존재하기 때문에, 굳이 DFS와 백트래킹을 사용하지 않고도 문제를 해결할 수 있습니다.

밑의 코드에 DFS, 백트래킹을 사용한 코드와 itertools 모듈의 combinations, permutations를 사용한 코드 모두 작성해놨으니 한번 비교해 보시면 좋을 것 같습니다.

---

3) 코드

 

* Python 코드(DFS, 백트래킹 사용)

import sys
input = sys.stdin.readline
 
 
def dfs(index, people, stack, visit):
    global team
 
    if len(stack) == len(people) // 2:
        team.append(stack[:])
        return
        
    for i in range(index, len(people)):
        if not visit[i]:
            stack.append(people[i])
            visit[i] = True
            dfs(i, people, stack, visit)
            stack.pop()
            visit[i] = False
 
 
N = int(input())
people = [x for x in range(N)]
stack = []
visit = [False] * N
S = [list(map(int, input().split())) for x in range(N)]
team = []
 
dfs(0, people, stack, visit)
 
limit = len(team)
gap = 9001
for i in range(limit // 2):
    sum1 = 0
    sum2 = 0
    for j in range(len(team[i])):
        for k in range(j + 1, len(team[i])):
            sum1 += S[team[i][j]][team[i][k]] + S[team[i][k]][team[i][j]]
            sum2 += S[team[limit - i - 1][j]][team[limit - i - 1][k]] + S[team[limit - i - 1][k]][team[limit - i - 1][j]]
    if gap > abs(sum1 - sum2):
        gap = abs(sum1 - sum2)
 
print(gap)

---

* Python 코드(itertools 모듈 사용)

import sys
input = sys.stdin.readline
from itertools import combinations as C, permutations as P
 
people = [x for x in range(int(input()))]
S = [list(map(int, input().split())) for x in range(len(people))]
team = list(C(people, len(people) // 2))
 
limit = len(team)
gap = 9001
for i in range(limit // 2):
    sum1 = 0
    sum2 = 0
    startTeam = list(P(team[i], 2))
    linkTeam = list(P(team[limit - i - 1], 2))
    for j in range(len(startTeam)):
        sum1 += S[startTeam[j][0]][startTeam[j][1]]
        sum2 += S[linkTeam[j][0]][linkTeam[j][1]]
    if gap > abs(sum1 - sum2):
        gap = abs(sum1 - sum2)
 
print(gap)

---