백트래킹
백트래킹Backtracking이란 알고리즘보다는 각 노드를 DFS 방식으로 방문하면서 조건에 맞는지를 확인하고(Promising), 조건에 맞지 않는 노드는 앞으로의 탐색 대상에서 제외(Pruning)하는 전략이다.
스타트와 링크
풀이 코드
#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int point[25][25];
bool visited[25];
int answer=987654321;
int calculatePoint(int cur, bool flag){
int sum=0;
for(int i=0;i<cur;i++){
if(visited[i] == flag){
sum+=point[cur][i];
sum+=point[i][cur];
}
}
return sum;
}
void dfs(int cur, int depth){
// 2-1. (조건)팀을 절반으로 나눴다면 팀별 능력치 계산하기
if(depth == N/2){
int start=0, link=0;
for(int i=0;i<N;i++){
if(visited[i] == true){
start +=calculatePoint(i, true);
}
else {
link +=calculatePoint(i, false);
}
}
answer = min(answer, abs(start-link));
return;
}
// 2-2. 그렇지 않다면 팀원 선정 계속하기
for(int i=cur;i<N;i++){
if(visited[i] == false){
visited[i] = true;
dfs(i, depth+1);
visited[i] = false;
}
}
}
int main() {
// 1. 입력받기
cin >> N;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin >> point[i][j];
}
}
fill_n(visited, N, false); // visited 배열 초기화
// 2. DFS로 모든 팀조합 탐색하기
dfs(0,0);
cout << answer;
}스스로 풀이 하지 못한 이유
한 시간 가량 문제 풀이를 진행했음에도 문제를 해결하지 못해 다른 코드를 참고해서 힌트를 얻었다.
나는 알고리즘 스터디의 백트래킹 챕터로서 이 문제를 풀게 되었기 때문에 이 문제의 알고리즘이 백트래킹인 줄 알고 개념 공부를 선행했다.
하지만 어렵지 않은 문제였음에도 조건을 확인 해서 가지치기를 진행해야 한다는 백트래킹의 특성에 너무 매몰되어 풀이 방식을 복잡하게 생각했던 탓에 문제를 풀지 못했던 것 같다.
앞으로는 문제 개념 공부보다는 풀이를 먼저 진행해볼까 생각도 했지만, 그렇기엔 또 모르는 유형이 많은지라...(다음 챕터는 다익스트라) 한 번 더 모르는 알고리즘 개념 공부를 먼저 하되, 문제를 풀이할 때 의식적으로 그 틀에 고정되지 않도록 애써보기로 했다. 그래도 안되면 그때 또 새로운 방법을 생각해봐야지.
참고 자료
pizz@ttang