백준(baekjoon) 14889번: 스타트와 링크(실버 2, 파이썬 PYTHON) - 백트래킹

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

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

예를 들어, 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이 되고 이 값이 최소이다.

 

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

14889번: 스타트와 링크

 

import sys

N=int(sys.stdin.readline())
people=[]
start_team=[]
diff=-1

for _ in range(N):
  people.append(list(map(int,sys.stdin.readline().split())))

def dfs(num): 
  global N,people,start_team,diff
  if(num==N//2): 
    start=0
    link=0
    link_team=[]
    for x in range(N): 
      if(x not in start_team): 
        link_team.append(x) 
    for x in range(N//2-1):
      for y in range(x+1,N//2):
        start+=(people[start_team[x]][start_team[y]]+people[start_team[y]][start_team[x]])
        link+=(people[link_team[x]][link_team[y]]+people[link_team[y]][link_team[x]])
    if(diff==-1 or diff>abs(start-link)): 
      diff=abs(start-link) 
  else: 
    for x in range(N):
      if(x not in start_team and (len(start_team)==0 or start_team[len(start_team)-1]<x)):  
        start_team.append(x) 
        dfs(num+1)
        start_team.remove(x) 

dfs(0)
print(diff)

 

※ 백트래킹

 

 

● 먼저 N을 입력받고, 표 안의 값들을 2차원 배열 people에 저장한다.

문제에 주어진 사람의 번호는 1부터 시작하지만 배열 인덱스는 0부터 시작하므로 번호도 0부터 시작한다고 가정하자.

 

함수 dfs() 를 정의해주자.

 

● 이 때 매개변수는 스타트 팀을 나타내는 start_team 배열에 들어가있는 요소의 수를 나타낸다.

 

● 만약 매개변수 num의 값이 총 인원수 N의 절반에 도달하면 팀이 다 짜여진 것이므로, for문을 활용하여 인원의 번호인 0부터 N-1 값 중 start_team 배열에 들어가 있지 않은 값을 link_team에 append 해준다.

 

● 그 후 문제 조건에 맞게 각 팀의 능력치를 계산해 준 뒤, diff변수가 아직 초기값으로 넣어줬던 -1이거나 능력치 차이가 현재 diff의 값보다 작으면 diff 값을 능력치 차이로 갱신해준다.

 

● 만약 매개변수 num의 값이 총 인원수 N의 절반보다 작다면 0부터 N-1 중

현재 start_team의 요소가 아니고 (and) (start_team이 빈 배열 (or) 현재 확인하는 값이 start_team의 끝 요소보다 크다면) (start_team의 인원 번호가 오름차순이 될 수 있도록 하여 중복 계산 방지) start_team에 이 값을 append 해준 뒤, start_team의 인원이 1명 늘었으므로 dfs(num+1) 을 호출해준다.

 

● 다 끝나면 넣어주었던 번호를 다시 remove 해주면 문제가 해결된다!

 

 

결과