[DFS 2번(단순, 백트래킹)] 백준 캐슬 디펜스 17135 C++

 

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

#include <bits/stdc++.h>

using namespace std;

int n, m, d, ans, board[17][17];

bool shoot(int x, int y, int copyBoard[][17]) { // 궁수 위치 (x, y)
	for (int i = 1; i <= d; i++) {
		for (int j = 1; j <= i; j++) { // (i-j)가 커야 왼쪽부터
			int newX = x - (i - j);
			int newY = y - j;

			if ((newX <= 0) | (newY <= 0)) continue; // 0 이하
			if (copyBoard[newY][newX]) {
				if (board[newY][newX]) {
					board[newY][newX] = 0;
					return 1;
				}
				return 0;
			}
		}

		for (int j = i; j > 0; j--) { // (i-j)가 작아야 왼쪽부터
			int newX = x + (i - j);
			int newY = y - j;

			if ((newX > m) | (newY <= 0)) continue;
			if (copyBoard[newY][newX]) {
				if (board[newY][newX]) {
					board[newY][newX] = 0;
					return 1;
				}
				return 0;
			}
		}
	}

	return 0;
}

void cal(int arrow, int depth, int val) {
	bool flag = true;
	for (int i = 1; i < depth; i++) {
		for (int j = 1; j <= m; j++) {
			if (board[i][j]) flag = false;
		}
	}

	if ((depth == 1) || (flag)) {
		ans = max(ans, val);
		return;
	}

	int copyBoard[17][17];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			copyBoard[i][j] = board[i][j];
		}
	}

	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		if ((arrow & (1 << i)) != (1 << i)) continue;
		if (shoot(i, depth, copyBoard)) cnt++;
		if (cnt == 3) break;
	}

	cal(arrow, depth - 1, val + cnt);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			board[i][j] = copyBoard[i][j];
		}
	}
}

void dfs(int arrow, int start) {
	if (start > m) return;

	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		if ((arrow & (1 << i)) == (1 << i)) cnt++;
	}

	if (cnt == 3) {
		cal(arrow, n + 1, 0);
		return;
	}

	for (int i = start + 1; i <= m; i++) {
		if ((arrow & (1 << i)) == (1 << i)) continue;
		int temp = (arrow | (1 << i));
		dfs(temp, i);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> d;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
		}
	}

	dfs(0, 0);
	cout << ans;
}

 

※ BFS, DFS 이용 풀이

#include <bits/stdc++.h>

using namespace std;

int n, m, d, ans, board[17][17];
int dx[3] = { -1, 0, 1 };
int dy[3] = { 0, -1, 0 };
bool visited[17][17];

struct Info {
	int x, y, dist;
};
queue<Info> q;
Info info;

void findClosest(int newX, int newY, int dist) {
	if ((info.dist != -1) && (dist > info.dist)) return;
	if ((info.x == -1) || (newX < info.x)) {
		info.x = newX;
		info.y = newY;
		info.dist = dist;
	}
}

bool shoot(int x, int y, int copyBoard[][17]) { // 궁수 위치 (x, y)
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			visited[i][j] = false;
		}
	}
	
	q.push({ x,y,1 });
	visited[y][x] = true;
	info = { -1, -1, -1 };

	while (!q.empty()) {
		int popX = q.front().x;
		int popY = q.front().y;
		int dist = q.front().dist;
		q.pop(); // 먼저 빼기
		
		if (dist > d) continue;
		if (copyBoard[popY][popX]) findClosest(popX, popY, dist);
		
		for (int i = 0; i < 3; i++) {
			int newX = popX + dx[i];
			int newY = popY + dy[i];
			
			if ((newX == 0) || (newY == 0) || (newX > m)) continue;
			if (visited[newY][newX]) continue;
			visited[newY][newX] = true;
			q.push({ newX, newY, dist + 1 });
		}
	}
	
	if ((info.x == -1) || (board[info.y][info.x]) == 0) return 0;
	else {
		board[info.y][info.x] = 0;
		return 1;
	}
}

void cal(int arrow, int depth, int val) {
	bool flag = true;
	for (int i = 1; i < depth; i++) {
		for (int j = 1; j <= m; j++) {
			if (board[i][j]) flag = false;
		}
	}

	if ((depth == 1) || (flag)) {
		ans = max(ans, val);
		return;
	}

	int copyBoard[17][17]; // 지역 변수로 선언
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			copyBoard[i][j] = board[i][j];
		}
	}

	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		if ((arrow & (1 << i)) != (1 << i)) continue;
		if (shoot(i, depth - 1, copyBoard)) cnt++;
		if (cnt == 3) break;
	}


	cal(arrow, depth - 1, val + cnt);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			board[i][j] = copyBoard[i][j];
		}
	}
}

void dfs(int arrow, int start) {
	if (start > m) return;

	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		if ((arrow & (1 << i)) == (1 << i)) cnt++;
	}

	if (cnt == 3) {
		cal(arrow, n + 1, 0);
		return;
	}

	for (int i = start + 1; i <= m; i++) {
		if ((arrow & (1 << i)) == (1 << i)) continue;
		int temp = (arrow | (1 << i));
		dfs(temp, i);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> d;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
		}
	}

	dfs(0, 0);
	cout << ans;
}