14889번 스타트와 링크(DFS, 2차원 배열 완탐) - ☆

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

s : 능력치 2차원 배열 / sel : start와 link팀을 나누기 위한 check 배열 / start, link : 하나의 조합에서 각 스타트팀과 링크팀의 능력치 합 / lower : 두팀의 능력치 합 차이의 최소값

답코드 참고 : https://fjvbn2003.tistory.com/434

전략 : dfs를 이용하여 팀의 조합을 구한다음 N/2명의 팀을 꾸린다. 각 팀별 능력치를 합산한다.

※주의사항

1. sel과 같은 조합 체크 배열의 특징을 보면 최대 depth까지 들어갔을때, sel[i]가 1, 0으로 나뉘는데, 이문제에선 그게 두팀으로 이미 나뉜 조합이라 생각할 수 있다.

2. 2차원 배열에서 2중 for문을 돌려서 완탐을 할때, 이미 지나간 요소는 다시 돌아가지 않으므로 이 특징을 생각해서 start와 link팀의 능력치 합을 구할 때, s[i][j]+s[j][i] 와 같은 중복이 생기는 실수를 하지 않도록 한다.

Code