[프로그래머스] PCCP 모의고사 1회 2번 - 체육대회 JavaScript

문제 설명

당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다. 당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다. 학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다. 당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.

다음은 당신의 반 학생이 5명이고, 종목의 개수가 3개이며, 각 종목에 대한 학생들의 능력치가 아래 표와 같을 때, 각 종목의 대표를 뽑는 예시입니다.

	테니스	탁구	수영
석환	40	10	10
영재	20	5	0
인용	30	30	30
정현	70	0	70
준모	100	100	100

테니스 대표로 준모, 탁구 대표로 인용, 수영 대표로 정현을 뽑는다면, 세 명의 각 종목에 대한 능력치의 합은 200(=100+30+70)이 됩니다.

하지만, 테니스 대표로 석환, 탁구 대표로 준모, 수영 대표로 정현을 뽑는다면 세 명의 각 종목에 대한 능력치 합은 210(=40+100+70)이 됩니다. 이 경우가 당신의 반의 각 종목 대표의 능력치 합이 최대가 되는 경우입니다.

당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.

---

제한사항

• 1 ≤ ability의 행의 길이 = 학생 수 ≤ 10
• 1 ≤ ability의 열의 길이 = 종목 수 ≤ ability의 행의 길이
• 0 ≤ ability[i][j] ≤ 10,000
  • ability[i][j]는 i+1번 학생의 j+1번 종목에 대한 능력치를 의미합니다.

---

입출력 예

ability	result
[[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]]	210
[[20, 30], [30, 20], [20, 30]]	60

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 1번 학생이 2번 종목을, 2번 학생이 1번 종목의 대표로 참가하는 경우에 대표들의 해당 종목에 대한 능력치의 합이 최대가 되며, 이는 60입니다.

---

문제풀이

깊이 우선 탐색(DFS)을 사용하여 주어진 능력치 배열 ability로부터 각 종목의 대표를 선택하여 최대 능력치 합을 찾는 함수를 작성한다.

1. students 변수는 학생 수, sports 변수는 종목 수를 나타낸다. visited 배열은 학생들의 방문 여부를 기록하기 위한 배열이다. maxSum 변수는 최대 능력치 합을 저장할 변수로 초기값은 0으로 설정된다.
2. 깊이 우선 탐색을 수행하는 함수를 작성한다. count 매개변수는 현재 선택한 종목의 개수, sum 매개변수는 현재까지 선택한 대표들의 능력치 합을 나타낸다.
3. count 값이 sports 값과 같아지면 모든 종목에 대한 대표가 선택된 것이므로, 현재 sum 값과 maxSum 값을 비교하여 능력치 합의 최댓값을 업데이트한다.
4. 그렇지 않은 경우, 학생들을 반복하면서 아직 방문하지 않은 학생을 선택하고 visited[i]를 true로 표시하여 해당 학생을 대표로 선택한다. 그리고 dfs 함수를 재귀적으로 호출하여 다음 종목을 선택하도록 한다. 선택이 완료되면 visited[i]를 다시 false로 변경하여 해당 학생을 선택 해제한다.
5. dfs(0, 0)을 호출하여 탐색을 시작하고, 최종적으로 maxSum에 저장된 최대 능력치 합을 반환한다.

이 코드는 가능한 모든 대표 선발 조합을 탐색하여 최대 능력치 합을 찾는 브루트 포스 방식으로 동작한다. 단, 브루트 포스는 문제의 크기가 작을 때 주로 사용된다. 문제 공간이 크거나 입력 크기가 큰 경우에는 브루트 포스로 모든 경우의 수를 계산하는 데 필요한 계산 시간이 지나치게 많아질 수 있다. 이 문제에서는 ability 배열의 행의 길이(학생 수)가 10이하였기 때문에 완전탐색이 가능하다.

따라서, 위 문제는 DFS를 사용하여 가능한 모든 대표 선발 조합을 탐색하는 완전탐색, 브루트 포스 방식의 문제로 볼 수 있다.

function solution(ability) {
  let students = ability.length; // 학생 수
  let sports = ability[0].length; // 종목 수
  let visited = Array(students).fill(false); // 방문 여부 기록 배열
  let maxSum = 0; // 최대 능력치의 합을 저장할 변수

	// sum: 현재까지 선택한 대표들의 능력치 합, count: 현재 선택한 종목의 개수
  const dfs = (sum, count) => {
    if (count === sports) {
      maxSum = Math.max(maxSum, sum);
      return;
    }
    for (let i = 0; i < students; i++) {
      if (!visited[i]) {
        visited[i] = true; // 해당 학생을 대표로 선택
        dfs(sum + ability[i][count], count + 1); // 다음 종목 선택 진행
        visited[i] = false; // dfs 종료 후, 해당 학생 선택 해제
      }
    }
  };

  dfs(0, 0);

  return maxSum;
}