[백준] 26169번 : 세 번 이내에 사과를 먹자

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 DFS 방식으로 풀었다. 한 경로로 깊게 들어가면서 depth를 체크하고, 해당 경로의 depth가 3에 이르렀을 때 사과를 2개 이상 먹을 수 있는지 판별하고자 한다.

1) 각 칸에 대해 (y좌표, x좌표, 칸의 값)을 저장하는 tuple들을 저장하는 큐를 선언한다.
2) 각 칸의 방문 여부 체크하는 vector를 5 * 5 크기로 false를 넣어 초기화한다.
3) 첫 칸에 대해 DFS 함수를 실행한다.
: 현재 칸을 방문 처리한 후, 해당 칸의 위, 아래, 왼쪽, 오른쪽 칸을 체크해 이 칸들이 이전에 방문한 적 없고, 칸의 값이 -1이 아니면(이동 가능 조건) 다음 칸에 대해 DFS를 재귀 호출한다.

• 재귀호출 할 때 다음 칸의 값에 따라 매개변수가 달라진다.
  • 다음 칸의 값이 1일 때 (사과 획득) : depth와 count를 1씩 늘려서 DFS를 호출한다.
  • 다음 칸의 값이 1이 아닐 때 : depth만 늘리고, count는 그대로 둔다.

4) 또한 DFS의 첫 부분에서 depth와 count를 체크한다.

• 현재까지의 depth가 3 이하이고 count가 2 이상인 경로일 경우
  : 가능 여부를 판별하는 bool 변수인 isMoreThan2 변수를 true로 변경하고 즉시 return한다.

• 현재까지의 depth가 3 이상이고 count가 2 미만인 경로일 경우
  : 더 이상 경로를 진행해도 불가능한 경로이기 때문에 즉시 return 한다.

5) 가능한 모든 경로를 방문해 최초 호출한 DFS가 끝날 때, isMoreThan2 변수의 값이 true인지 false인지에 따라 1 또는 0을 출력한다. (가능한 경로가 하나라도 있었다면 isMoreThan2의 값이 true일 것이고, 하나도 없다면 false일 것이다.)

❗더 이상 방문할 칸이 없어 되돌아 갈 때(즉, DFS 함수가 끝날 때)는 visited를 false로 변경해야 한다.
➡️ 다른 경로와 해당 칸을 공유하는 경우에 visited를 그대로 놔두면 이미 방문되어있는 것으로 처리되어 다른 경로에서 해당 칸에 접근할 수 없기 때문이다.

🖥️ 풀이 코드

#include <bits/stdc++.h>

using namespace std;
typedef tuple<int, int, int> tiii;

bool isMoreThan2 = false;
vector<bool> set_bool(5, false);
vector<vector<bool>> visited(5, set_bool);

void DFS(int y, int x, vector<tiii> arr, int depth, int count)
{
	// 방문 처리
	visited[y][x] = true;

	int currentDepth = depth;
	int currentCount = count;

	if (depth <= 3 && count >= 2)
	{
		isMoreThan2 = true;
		return;
	}

	if (depth >= 3 && count < 2)
		return;

	// 위로 이동
	if (y > 0 && !visited[y - 1][x] && get<2>(arr[(y - 1) * 5 + x]) != -1)
	{
		if (get<2>(arr[(y - 1) * 5 + x]) == 1)
			DFS(y - 1, x, arr, currentDepth + 1, currentCount + 1);
		else
			DFS(y - 1, x, arr, currentDepth + 1, currentCount);	
	}

	// 아래로 이동
	if (y < 4 && !visited[y + 1][x] && get<2>(arr[(y + 1) * 5 + x]) != -1)
	{
		if (get<2>(arr[(y + 1) * 5 + x]) == 1)
			DFS(y + 1, x, arr, currentDepth + 1, currentCount + 1);
		else
			DFS(y + 1, x, arr, currentDepth + 1, currentCount);
	}

	// 왼쪽으로 이동
	if (x > 0 && !visited[y][x - 1] && get<2>(arr[y * 5 + x - 1]) != -1)
	{
		if (get<2>(arr[y * 5 + x - 1]) == 1)
			DFS(y, x - 1, arr, currentDepth + 1, currentCount + 1);
		else
			DFS(y, x - 1, arr, currentDepth + 1, currentCount);
	}

	// 오른쪽으로 이동
	if (x < 4 && !visited[y][x + 1] && get<2>(arr[y * 5 + x + 1]) != -1)
	{
		if (get<2>(arr[y * 5 + x + 1]) == 1)
			DFS(y, x + 1, arr, currentDepth + 1, currentCount + 1);
		else
			DFS(y, x + 1, arr, currentDepth + 1, currentCount);
	}
	
    visited[y][x] = false;	// 다른 경로와 해당 노드를 공유하는 경우를 위해서 visited를 false로 되돌려줌.
    
	if (currentDepth == 0)
	{
		if (isMoreThan2)
			cout << 1;
		else
			cout << 0;
	}
}

int main()
{	
	vector<tuple<int, int, int>> arr(25);	// 각 칸에 대해 (y좌표, x좌표, 칸 종류) 저장

	// 맵 입력하기
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			int n;
			cin >> n;	// cin은 입력 버퍼에서 공백 이전까지만 값을 가져옴. 이후 cin을 호출하면 입력하지 않아도 자동으로 입력 버퍼에서 남아있는 값을 가져옴.
						// 따라서 0 0 1 0 0 을 한 번 입력 시, 5번의 반복문 동안 n에 0 0 1 0 0 이 차례대로 할당됨.
			arr[i * 5 + j] = tiii(i, j, n);
		}
	}

	// 현재 위치 입력하기
	int y, x;
	cin >> y;
	cin >> x;
	cin.ignore();

	DFS(y, x, arr, 0, 0);
}