오늘은 backtrack 마지막 문제, 스타트와 링크를 풀었다.
총 N명의 사람 중 N/2명을 고르는 것이므로 만큼의 경우의 수를 봐 주어야 한다.
총 1부터 8까지 사람이 있으면
1 2 3 4
1 2 3 5
1 2 3 6
1 2 3 7
1 2 3 8
1 2 4 5
1 2 4 6
1 2 4 7
...
2 3 4 5
2 3 4 6
...
대충 이런식으로 조합 경우의 수가 정해지기 때문에, 제일 최근에 탐색한 사람 다음 사람부터 DFS를 실행했다.
그리고 N이 짝수인 것은 보장되었기 때문에 depth가 N/2가 되면 점수 계산을 진행한다. 조금 더 깔끔한 코드도 존재할 수 있겠지만 아직 그 정도의 실력이 안 되는 것 같다.
전체적인 구조는 다른 backtrack 문제들과 동일하다. depth가 일정 깊이에 도달하면 stop하고 점수를 계산한다. 안 그러면 내가 원하는 DFS를 진행한다. 위에 언급한 것처럼 '조합의 특성'을 코드로 생각하는 게 좀 어려웠다.
void DFS(vector<vector<int>>& stat, vector<bool>& people_in_start, int depth, int N, int& stat_difference, int recently_searched_people) { if (depth == N / 2) { int team_stat_start = 0; int team_stat_link = 0; vector<int> team_start; vector<int> team_link; for (int i = 0; i < N; i++) { if (people_in_start[i] == true) team_start.push_back(i); else team_link.push_back(i); } for (int i = 0; i < team_start.size(); i++) { for (int j = i + 1; j < team_start.size(); j++) { team_stat_start += stat[team_start[i]][team_start[j]]; team_stat_start += stat[team_start[j]][team_start[i]]; } } for (int i = 0; i < team_link.size(); i++) { for (int j = i + 1; j < team_link.size(); j++) { team_stat_link += stat[team_link[i]][team_link[j]]; team_stat_link += stat[team_link[j]][team_link[i]]; } } stat_difference = min(stat_difference, abs(team_stat_link-team_stat_start)); return; } else { // DFS for (int i = recently_searched_people+1; i < N; i++) { people_in_start[i] = true; DFS(stat, people_in_start, depth + 1, N, stat_difference, i); people_in_start[i] = false; } // 처음에는 1부터 n/2까지, 그다음엔 1부터 n/2-1 + n/2+1, n/2+2, ... // 이 문이 생각보다 생각하기 어려웠음. 조합을 떠올리기 } }
이제 입력받고 실행 함수를 적으면 끝일 것이다.
void solve() { int N; cin >> N; vector<vector<int>> stat(N, vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> stat[i][j]; } } int stat_difference = 1000000000; vector<bool> people_in_start(N); DFS(stat, people_in_start, 0, N, stat_difference, 0); cout << stat_difference; }
'PS > Algorithm' 카테고리의 다른 글
2020/07/08 공부 - dynamic programming (0) | 2022.06.21 |
---|---|
2020/07/07 공부 - dynamic programming (0) | 2022.06.21 |
2020/07/06 공부 - dynamic programming (0) | 2022.06.21 |
2020/07/04 공부 - backtracking (0) | 2022.06.21 |
2020/07/02 공부 - backtracking (0) | 2022.06.21 |