SWEA 1494번 D4 사랑의 카운슬러 C++ 백트래킹, DFS

리뷰

 

문제 풀이

1. 전역변수로 테케의 수 tc와 지렁이의 수 n, 이동과 대기한 수를 나타낼 Move, Stay 정답 변수 ans를 설정한다.
2. init 함수를 통해 ans를 최대한 큰 값, Move와 Stay를 0으로 초기화 해준다.
3. input 함수를 통해 n값과 n개의 지렁이의 좌표를 Pos 구조체를 활용하여 pos배열에 저장해 준다.
4. dfs 함수를 통해 각 지렁이가 짝을 지었을때의 좌표 벡터값을 구해줄 것이다.
5. 매개변수로는 지렁이 인덱스를 나타낼 level과 x좌표의 값 sumX, y좌표의 값 sumY를 전달해 준다.
6. Move와 Stay가 각각 n / 2보다 작을 경우 Move와 Stay를 각각 증가시켜주고 재귀를 진행하면 된다.
7. 재귀를 전달할땐 level인덱스의 x, y좌표를 sumX, sumY에 더해주고 level을 1 증가시킨다.
8. Move와 Stay가 동일하고 모든 지렁이를 선택했을때가 기저조건이 된다, ans를 최소값으로 갱신해 준다.
9. 탐색을 마친 뒤 ans에 저장되어 있는 값을 출력해 주면 된다.

 

참고 사항

n은 짝수로 주어짐이 명시되어 있으므로 값은 항상 출력이 된다.

벡터의 값은 최악의 경우 10만 * 10만으로 int범위를 넘어설 수 있기 때문에 long long타입으로 설정해 준다.

 

정답 코드

#include<iostream>
#define ll long long

using namespace std;
int tc, n, Move, Stay;
ll ans;

struct Pos {
	int x, y;
};

Pos pos[21];

void init() {
	ans = 9e15;
	Move = 0;
	Stay = 0;
}

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> pos[i].x >> pos[i].y;
}

void dfs(int level, ll sumX, ll sumY) {
	if (Move == n / 2 && Stay == n / 2) {
		ans = min(ans, sumX * sumX + sumY * sumY);
		return;
	}

	if (n / 2 > Move) {
		Move++;
		dfs(level + 1, sumX + pos[level].x, sumY + pos[level].y);
		Move--;
	}

	if (n / 2 > Stay) {
		Stay++;
		dfs(level + 1, sumX - pos[level].x, sumY - pos[level].y);
		Stay--;
	}
	return;
}

void solution() {
	dfs(0, 0, 0);
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		solution();
		cout << "#" << t <<" " << ans << "\n";
	}
}