[백준 알고리즘][완전탐색][DFS][백트래킹] 14889번 스타트와 링크

문제 정의

N명이 주어졌을 때, N/2명으로 두 팀을 나눠야 한다. S[i][j]는 i번 사람이 j번 사람과 같은 팀에 속했을 때의 능력치를 뜻하는데, 두 팀의 능력치 차이가 최소가 되는 경우를 구해야 한다. 

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14889)

문제 풀이

 N이 최대 20이므로 완전탐색을 통해 N/2명의 팀을 짜는 모든 경우를 탐색해도 시간이 오래 걸리지 않는다. 완전 탐색을 통해서 가장 비슷한 능력치를 가지는 쌍을 구하도록 한다. 앞서 이 문제를 풀기 전 로또 문제를 풀었던 방식을 응용해서 N/2명의 두 팀을 나눌 수 있다. DFS를 통해서 N/2명이 되었을 때 그 팀의 능력치를 구하고, N/2명에 속하지 않은 다른 팀원들이 속하는 팀의 능력치를 구해서 능력의 차이를 구한다. 완전탐색을 통해서 모든 경우를 봐야하므로 생각보다 문제 풀기가 번거롭고 까다롭다.(라고 썼었는데 완전탐색이라서 오히려 더 쉽다.) 예제의 경우는 총 4명을 2명, 2명으로 나누는 문제라 간단해보이지만 만약 8명의 팀원이 있다면 4명, 4명으로 나눈 다음 4명 중 한명에 대해서 다른 팀원들과 같은 팀이 되었을 때의 능력치를 전부 더해야 하는 과정이 필요하다. 로또 문제가 정말 팀을 나누는 정도만 해보는 문제였다면 이 문제는 그 문제를 통해 응용해볼 수 있는 문제이다. 앞에 로또 문제를 풀 때도 나는 인접리스트를 만들었었는데, 어차피 이런 문제에서는 그래프로 생각을 해보면 모든 정점들이 연결되어있기때문에 굳이 인접리스트를 만들 필요가 없다. 방향성이 있지 않고, 모두 연결되어 있다. 4명으로 예를 들면 어차피 1번에서는 2, 3, 4번을 갈 수 있고 그다음 2번에 오면 어차피 1에서 2로 가는 경우는 앞에서 탐색했기때문에 2에서는 3, 4로 가는 경우만 탐색하면된다. 따라서 DFS를 탐색할 때 해당하는 번호에서 다음번호로 계속해서 탐색을 해나가면 된다. 로또 문제를 풀듯이 풀면 스택에 N/2만큼 쌓였을 때 스타트팀과 링크팀의 능력치를 각각 계산하고, 두 능력치의 차이가 최소값일 경우에만 갱신시키며 저장한다.