[알고리즘] 백준 14889번: 스타트와 링크

nko·2021년 1월 31일

알고리즘

목록 보기

1/4

백준 14889번: 스타트와 링크

문제 해석

축구를 하기 위해 모인 사람 N명

N/2명으로 이루어진 스타트 팀과 링크 팀

팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합

i번 사람과 j번 사람이 같은 팀이면, 팀에 더해지는 능력치는 Sij + Sji

두 팀의 능력치 차이의 최소를 원함

주요 로직

/*
*	select[N]은 전체 인원의 선택 유무 확인을 위한 변수
*	cnt는 몇 명이 선택되었는지 확인하기 위한 변수
*	pos는 현재 내가 누구인지 확인하기 위한 변수
*/               

                
dfs(pos, cnt) {
// 기저조건: N/2의 인원이 포함된 한 개의 팀 완성
  if (cnt == N/2) {
      1. 나머지 팀 완성
      2. 각 팀의 능력치 구하기
      3. 차이 구하고 min 체크
  }

  for i = pos ~ N {
      select[i] = 1; // 선택
      dfs(i, cnt + 1); // 선택해서 재귀 들어감
      select[i] = 0; // 선택 안 함
  }
}

반복문에서 pos부터인 이유는 선택된 나부터 그 후의 사람만 보면 되기 때문이다.

나 이전은 항상 선택되어 있기 때문에 신경 쓸 필요가 없다.

결론적으로, 재귀는 "나"만 보면 된다. (= 나는 내 할 일만 한다.)

0                   O                  X
		  /   \
1               O       X
	      /   \
2           O       X
		  /   \
3               O       X
		      /   \
4                   O       X
			  /   \
5                       O       X

문제를 풀기 위해 DFS가 동작하는 모습을 트리로 그린 것인데 0, 1, 2에서 모두 O가 된 후에는 더 깊이 들어가지 않아야 된다는 것을 확인할 수 있다.

그러므로 이 문제는 DFS에서 가지치기를 한 Backtracking 기법을 사용해서 풀어야 한다는 사실을 알게 됐다.

문제 해결

  #include <iostream>
  #include <vector>
  using namespace std;

  #define MAX_SIZE 21

  int N;
  bool selected[MAX_SIZE];
  int S[MAX_SIZE][MAX_SIZE];
  int answer = 1000000000; // 10억

  // pos번 선수를 선택한다, cnt는 선택한 수
  void DFS(int pos, int cnt) {
      // 기저조건 : N/2로 구성된 한 팀이 만들어짐
      if (cnt == N / 2) {
          vector<int> team_link, team_start;

          // 뽑혔으면 스타트 팀, 아니면 링크 팀
          for (int i = 1; i <= N; i++) {
              if (selected[i]) team_start.push_back(i);
              else team_link.push_back(i);
          }

          // 각 팀의 능력치 합 구하기
          int stat_start = 0, stat_link = 0;
          // 팀에 선택된 선수는 vector이기 때문에 0부터 시작
          for (int i = 0; i < team_start.size(); i++) {
              // team_start = [1,2,3]이므로 i+1부터 해야 (1,2) (1,3) (2,3) 의 조합이 만들어짐
              for (int j = i + 1; j < team_start.size(); j++) {
                  stat_start += S[team_start[i]][team_start[j]] + S[team_start[j]][team_start[i]];
                  stat_link += S[team_link[i]][team_link[j]] + S[team_link[j]][team_link[i]];
              }
          }

          // 두 팀의 차이 구해서 최소값 갱신
          answer = min(answer, abs(stat_start - stat_link));
          return;
      }

      // 팀 배정에서 중복이 일어난 경우를 막기 위해 N - 1까지, pos는 DFS로 넘어오기 전의 값을 기억해서 그 값보다 이전의 범위는 탐색하지 않게 하기 위해 필요
      // 두 팀의 차이를 보는 것이기 때문에 S(1,2,3) L(4,5,6)과 S(4,5,6) L(1,2,3)은 중복!
      for (int i = pos; i < N; i++) {
          selected[i] = true;
          DFS(i + 1, cnt + 1);
          selected[i] = false;
      }
  }

  int main() {
      ios_base::sync_with_stdio(false);
      cin.tie(0); cout.tie(0);

      cin >> N;
      for (int i = 1; i <= N; i++) {
          for (int j = 1; j <= N; j++) {
              cin >> S[i][j];
          }
      }
      DFS(1, 0); // pos는 1부터 cnt는 0부터 시작
      cout << answer << '\n';
      return 0;
  }

주의할 점

선수가 1 ~ N 으로 되어 있어서 입력과 반복문을 1부터 시작했는데 오히려 본인 스스로도 헷갈리고 좋지 않다고 판단되어 다음부터는 인덱스를 0으로 하는 것이 낫다고 생각된다.
DFS를 할 때, 넘겨주는 인자가 pos, cnt 두 가지가 있는데 여기서 pos는 DFS 안으로 들어가서 다음 선수를 선택하기 위해 +1을 해서 보내주고 cnt는 바로 위에서 selected[i] = true로 현재 선수를 선택했기 때문에 +1을 해줘야 한다.
Start [1,2,3] & Link [4,5,6] 인 경우의 두 팀의 능력치 합의 차이와 Start [4,5,6] & Link [1,2,3] 인 경우의 차이가 같기 때문에 이러한 중복되는 팀까지도 고려해서 쳐낸다면 시간이 절반으로 줄어들게 된다.
- 6C3 = 20 보다 5C3 = 5C2 = 10이 훨씬 조합의 수가 적기 때문에 효율적인 연산 가능.
- N-1(= 5)까지만 도는 이유는 6명 중에서 3명/3명으로 나누는 조합을 찾고 싶은거니까 5명까지만 보면 3명/2명으로 나뉜 후 부족한 1명은 남는 1명이 되기 때문에 굳이 볼 필요가 없기 때문이다.
- 즉, 명확한 5명까지만 찾으면 남는 1명을 찾아 링크 팀에 넣으면 되기 때문이다.

nko