백준 - 18428번 : 감시 피하기 (C++)

풀이 방법 : 백트래킹

각 위치에 장애물을 설치해서 설치한 장애물이 3개에 도달하면 선생의 위치에서 상하좌우 방향으로 학생의 위치에 도달가능한지 여부를 검사하면 된다.

입력 최댓값이 6밖에 안되므로 무식하게 다 설치해보는 식으로 해도 충분히 통과가 된다.

#include <iostream>
#include <vector>

using namespace std;

int N;
char Board[7][7] = {};
bool IsObstacle[7][7] = {};
bool IsEnable = false;
int SCnt = 0;

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


bool Check(int Y, int X, int SCnt)
{

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (Board[i][j] == 'T')
			{
				for (int k = 0; k < 4; ++k)
				{
					int NextY = i;
					int NextX = j;
					NextY += DirY[k];
					NextX += DirX[k];

					while (NextY < N && NextY >= 0
						&& NextX < N && NextX >= 0)
					{
						if (Board[NextY][NextX] == 'S')
						{
							return false;
						}

						else if (Board[NextY][NextX] == 'X')
						{
							if (IsObstacle[NextY][NextX])
								break;
						}

						NextY += DirY[k];
						NextX += DirX[k];
					}
				}
			}
		}
	}

	return true;
}

void DFS(int Y, int X, int Cnt)
{
	if (IsEnable)
		return;

	if (Y == N - 1 && X == N - 1)
		return;

	if (Cnt == 3)
	{
		IsEnable = Check(0, 0, 0);
		return;
	}

	if (X == N - 1)
	{
		DFS(Y + 1, 0, Cnt);

		if (Board[Y][X] == 'X')
		{
			IsObstacle[Y][X] = true;
			DFS(Y + 1, 0, Cnt + 1);
			IsObstacle[Y][X] = false;
		}
	}

	else
	{
		DFS(Y , X + 1, Cnt);
		if (Board[Y][X] == 'X')
		{
			IsObstacle[Y][X] = true;
			DFS(Y, X + 1, Cnt + 1);
			IsObstacle[Y][X] = false;
		}
	}
}


int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	cin >> N;

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

			if (Board[i][j] == 'S')
				++SCnt;
		}
	}

	DFS(0, 0, 0);

	if (IsEnable)
	{
		cout << "YES";
	}

	else
		cout << "NO";
}