백준 - 1103번 : 게임 (C++)

풀이 방법 : DFS + DP

그래프들의 내용을 탐색하면서 싸이클이 발생하는지의 유무를 따져줘야 하기 때문에 DFS를 선택했다. 백트래킹 하듯 해당 좌표에서 탐색 시작할 때 check 플래그를 true로 해주고 탐색이 끝나면 false로 해준다. 이렇게 해주면 중간에 check가 true인 놈을 만나면 싸이클이 발생가능하다는 것이므로 모든 탐색을 중단해주고 -1을 출력해주면 된다.

이렇게 해가면서 H를 만나거나 보드의 범위 바깥으로 벗어나면 Cnt의 Max값을 갱신해가면서 최댓값을 구해주면 된다.

그런데 이렇게 DFS로만 풀면 시간초과가 나길래 좀 더 생각해보았다.
결국에는 특정 좌표에서 이동 가능한 횟수는 이미 정해져 있다는 것을 떠올릴 수 있었다. 그러므로 해당 좌표에 도착했을 때의 최대 반복 횟수들을 저장하여 현재 탐색중인 케이스의 횟수보다 더 많은 이동을 이미 탐색한 경우 더이상 탐색할 필요가 없다고 판단할 수 있다.

#include <iostream>

using namespace std;

int DirX[4] = { 1,-1,0,0 };
int DirY[4] = { 0,0,1,-1 };

int N, M;
char Board[51][51] = {};
bool check[51][51] = {};
int  DP[51][51] = {};
int Max = 0;
bool IsLoop = false;

void DFS(int Cnt, int CurrentX, int CurrentY)
{
	if (IsLoop)
		return;

	if (DP[CurrentX][CurrentY] >= Cnt + 1)
		return;

	check[CurrentX][CurrentY] = true;

	for (int i = 0; i < 4; ++i)
	{
		int NextX = CurrentX + DirX[i] * ((int)Board[CurrentX][CurrentY] - 48);
		int NextY = CurrentY + DirY[i] * ((int)Board[CurrentX][CurrentY] - 48);

		if (NextX < 0 || NextX >= N ||
			NextY < 0 || NextY >= M)
		{
			DP[CurrentX][CurrentY] = max(DP[CurrentX][CurrentY], Cnt + 1);
			Max = max(Max, DP[CurrentX][CurrentY]);
			continue;
		}

		if (Board[NextX][NextY] == 'H')
		{
			DP[CurrentX][CurrentY] = max(DP[CurrentX][CurrentY], Cnt + 1);
			Max = max(Max, Cnt + 1);
			continue;
		}

		else
		{
			if (check[NextX][NextY])
			{
				IsLoop = true;
				check[CurrentX][CurrentY] = false;
				return;
			}

			else
				DFS(Cnt + 1, NextX, NextY);
		}
	}

	check[CurrentX][CurrentY] = false;
}


int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
			cin >> Board[i][j];
	}

	DFS(0, 0, 0);

	if (IsLoop)
		cout << -1;

	else
		cout << Max;

}

싸이클이 발생하는지 검사하기 위해 백트래킹 용으로 사용하는 check 플래그와 DP 테이블을 따로 생각해야하는 문제
되게 재밌게 풀었다.