(C++) 백준 26169: 세 번 이내에 사과를 먹자

문제 링크

이번 문제에서는 5 X 5보드에서 세 번 이하의 이동으로 사과를 2개 이상을 먹을 수 있는 지에 대한 문제입니다.

전형적인 DFS/BFS문제라 저는 평소에 자주 사용하던 DFS를 활용하여 풀어보았습니다.

먼저 고려해야할 것은 깊이가 3이면 마무리를 하자! 깊이를 파고 들어가서 3일 경우에 멈춰서 해당 칸까지 가는 데에 사과를 최대 몇까지 먹고 왔는지 확인합니다. 2개 이상 먹었다면 성공!
아니면 실패!입니다.

동서남북은

int xSign[4] = { 0,1,-1,0 };
int ySign[4] = { 1,0,0,-1 };

를 활용하여 for문으로 4개를 돌려 확인해주었습니다.

현재 좌표에서 동서남북으로 갔을 경우 다음 좌표가 각각 보드판에서 벗어나는지, 장애물이 있는 -1일 경우에는 그 그 방향으로 가지 않고 continue 해줍니다.

	for (int i = 0; i < 4; i++) {
			int xAfter = x + xSign[i];
			int yAfter = y + ySign[i];
			if (xAfter >= 5 || yAfter >= 5 || xAfter < 0 || yAfter < 0)
				continue;
			if (board[xAfter][yAfter] == -1)
				continue;

			if (board[xAfter][yAfter] == 1) {
				cost[xAfter][yAfter] = max(cost[xAfter][yAfter], cost[x][y] + 1);
			}
			else {
				cost[xAfter][yAfter] = max(cost[xAfter][yAfter], cost[x][y]);
			}
			board[x][y] = -1;
			DFS(xAfter, yAfter, depth + 1);
		}

다음 칸에 사과가 있다면 현재 칸까지 가는 데에 먹은 사과 + 1을 해줍니다. 만일, 다음 칸에 이미 계산된 사과 값이 있다면, 그 중 큰 값을 가져야하기 때문에 max를 활용하여 큰 값으로 업데이트 해줍니다.

그리고 이미 지나간 칸은 장애물이 있는 칸으로 여겨지기에 현재 칸을 -1로 바꿔줍니다.

그 다음 칸으로 재귀를 통해 넘어가 탐색하게 됩니다.

최종 코드

#include<iostream>
#include<vector>

using namespace std;

int xSign[4] = { 0,1,-1,0 };
int ySign[4] = { 1,0,0,-1 };

struct Val {
	int cost;
	int depth;
};
vector<vector<int>> board;
vector<vector<int>> cost;
bool ans;
void DFS(int x, int y, int depth){
	int temp = board[x][y];
	if (depth == 3) {
		if (cost[x][y] >= 2)
			ans = true;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int xAfter = x + xSign[i];
			int yAfter = y + ySign[i];
			if (xAfter >= 5 || yAfter >= 5 || xAfter < 0 || yAfter < 0)
				continue;
			if (board[xAfter][yAfter] == -1)
				continue;

			if (board[xAfter][yAfter] == 1) {
				cost[xAfter][yAfter] = max(cost[xAfter][yAfter], cost[x][y] + 1);
			}
			else {
				cost[xAfter][yAfter] = max(cost[xAfter][yAfter], cost[x][y]);
			}
			board[x][y] = -1;
			DFS(xAfter, yAfter, depth + 1);
		}
	}
}

int main() {
	for (int i = 0; i < 5; i++) {
		vector<int> temp;
		vector<int> temp2;
		for (int j = 0; j < 5; j++) {
			int num;
			cin >> num;
			temp.push_back(num);
			temp2.push_back(0);
		}
		cost.push_back(temp2);
		board.push_back(temp);
	}
	int startX, startY;
	cin >> startX >> startY;
	DFS(startX, startY, 0);
	cout << ans;
}