[G4] 백준 5913번 준규와 사과 C++ 백트래킹

리뷰

 

https://www.acmicpc.net/problem/5913

좌측 상단과 우측 하단에서부터 시작해 맵의 모든 지점을 방문하고 마지막에 동일한 좌표에서 만나는 문제

 

 

전역 변수

• v : 방문 정보를 저장할 2차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• k : 방문 불가한 좌표의 개수를 저장할 변수
• ans : 모든 조건을 만족하는 좌표의 개수

 

함수

1. print

void print(const pii& j, const pii& h) {
	cout << "\n";
	for (int i = 0; i < 5; ++i) {
		for (int k = 0; k < 5; ++k) {
			if (j.first == h.first && j.second == h.second) cout << 'm';
			else if (i == j.first && k == j.second) cout << 'j';
			else if (i == h.first && k == h.second) cout << 'h';
			else cout << v[i][k];
		}
		cout << "\n";
	}
}

 

디버깅용 함수

 

2. bt

void bt(const pii& j, const pii& h, int remain) {
	if (remain <= 0) {
		if (j.first == h.first && j.second == h.second) ++ans;
		return;
	}
	if (j.first == h.first && j.second == h.second) return;
	//print(j, h);

	int jx = j.first, jy = j.second;
	int hx = h.first, hy = h.second;
	for (int i = 0; i < 4; ++i) {
		int njx = jx + dx[i], njy = jy + dy[i];

		if (njx < 0 || njx > 4 || njy < 0 || njy > 4 || v[njx][njy]) continue;
		for (int k = 0; k < 4; ++k) {
			int nhx = hx + dx[k], nhy = hy + dy[k];

			if (nhx < 0 || nhx > 4 || nhy < 0 || nhy > 4 || v[nhx][nhy]) continue;
			v[njx][njy] = true;
			v[nhx][nhy] = true;
			bt({ njx, njy }, { nhx, nhy }, remain - 2);
			v[njx][njy] = false;
			v[nhx][nhy] = false;
		}
	}
}

 

백트래킹을 통해 맵을 방문하며 조건에 만족하는 모든 경우를 구하기 위한 함수

 

 

문제풀이

1. 변수 apple을 25로 초기화한다.
2. k값을 입력 받고, k개의 좌표를 입력 받아 v배열을 통해 해당 좌표를 방문처리 및 apple의 개수를 감소시킨다.
3. 초기 좌표인 0, 0과 4, 4에 방문 처리를한다.
4. bt함수에 {0, 0}, {4, 4}, apple-2를 매개변수로 전달하여 호출한다.
5. bt함수는 변수 j, h, remain에 각각 준규의 좌표, 해빈이의 좌표, 남은 사과 개수를 저장한다.
6. 기저 조건으로 remain이 0이하일 경우 j, h의 좌표가 같다면 ans를 증가한다. 이후 조건 여부와 상관없이 리턴한다.
7. 두번쨰 기저 조건으로 j, h의 좌표가 같다면 리턴한다.
8. 변수 jx, jy, hx, hy에 준규와 해빈이의 좌표를 파싱한다.
9. 4방향 탐색을 수행하며 준규가 이동할 좌표가 범위 밖이거나 이미 방문했다면 continue처리한다.
10. 4방향 탐색을 수행하며 해빈이가 이동할 좌표가 범위 밖이거나 이미 방문했다면 continue처리한다.
11. 둘 모두 유효한 좌표일 경우에만 방문 처리 후 이동한 좌표와 remain-2를 매개변수로 전달하여 재귀를 수행한다.
12. 재귀를 빠져나온 뒤엔 방문 처리한 내용을 원상 복구시켜준다.
13. 모든 백트래킹을 마친 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 0-based-indexing을 사용했으므로 k개의 좌표를 입력 받아 방문처리할때 좌표를 전위 감소 시켜주었다.
2. 시작점인 (0,0)과 (4,4)에는 항상 사과 나무가 심어져 있다. 따라서 초기 백트래킹 시 방문처리 및 apple을 감소시켰다.
3. 남은 사과가 없는데 j, h가 만난 경우만 ans를 증가, 아니라면 종료 처리하였다.
4. 또, 마지막을 제외하고 같은 칸에서 만날 수는 없다라는 조건이 있으므로 사과가 남아있는데 j, h가 만난 경우는 더 이상 탐색할 필요가 없어 조기종료해주었다.

 

정답 코드

#include<iostream>
using namespace std;
using pii = pair<int, int>;

bool v[5][5];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int k, ans;

void print(const pii& j, const pii& h) {
	cout << "\n";
	for (int i = 0; i < 5; ++i) {
		for (int k = 0; k < 5; ++k) {
			if (j.first == h.first && j.second == h.second) cout << 'm';
			else if (i == j.first && k == j.second) cout << 'j';
			else if (i == h.first && k == h.second) cout << 'h';
			else cout << v[i][k];
		}
		cout << "\n";
	}
}

void bt(const pii& j, const pii& h, int remain) {
	if (remain <= 0) {
		if (j.first == h.first && j.second == h.second) ++ans;
		return;
	}
	if (j.first == h.first && j.second == h.second) return;
	//print(j, h);

	int jx = j.first, jy = j.second;
	int hx = h.first, hy = h.second;
	for (int i = 0; i < 4; ++i) {
		int njx = jx + dx[i], njy = jy + dy[i];

		if (njx < 0 || njx > 4 || njy < 0 || njy > 4 || v[njx][njy]) continue;
		for (int k = 0; k < 4; ++k) {
			int nhx = hx + dx[k], nhy = hy + dy[k];

			if (nhx < 0 || nhx > 4 || nhy < 0 || nhy > 4 || v[nhx][nhy]) continue;
			v[njx][njy] = true;
			v[nhx][nhy] = true;
			bt({ njx, njy }, { nhx, nhy }, remain - 2);
			v[njx][njy] = false;
			v[nhx][nhy] = false;
		}
	}
}

int main() {
	int apple = 25;

	cin >> k;
	while (k--) {
		int x, y; cin >> x >> y;
		v[--x][--y] = true;
		--apple;
	}

	v[0][0] = true, v[4][4] = true;
	bt({ 0, 0 }, { 4, 4 }, apple - 2);
	cout << ans;
}