[백준] 골드5 : (18428) 감시 피하기

문제: https://www.acmicpc.net/problem/18428

 

문제에 주어지는 NxN 크기의 맵에서, N의 범위가 (3 ≤ N ≤ 6)이다.

이를 보면, 경우의 수가 굉장히 적기 때문에 브루트포스 알고리즘을 통해 풀 수 있음이 증명된다.

 

장애물은 비어있는 공간에만 설치할 수 있으므로, 모든 빈칸의 좌표를 벡터에 저장한다.

장애물이 3개가 들어갈 수 있는 모든 경우의 수를 탐색(3중 for문)

 

각 장애물을 놨을 때의 모든 선생님의 위치에서 가로 세로로 확인하여 학생과 만나는지 확인한다.

학생과 만나면 바로 반환하고, 함수가 끝날 때 까지 학생과 만나지 못하면 해당 장애물이 정답이므로 끝낸다.

#include <iostream>
#include <vector>
using namespace std;

int dy[]{ -1, 0, 1, 0 };
int dx[]{ 0, 1, 0, -1 };

int N;
vector<pair<int, int>> O, S, T;

bool Func(const vector<vector<int>>& Map, const pair<int, int>& O1, const pair<int, int>& O2, const pair<int, int>& O3)
{
	for (const auto& i : T)
	{
		int y = i.first, x = i.second;

		for (int j = 0; j < 4; ++j)
		{
			while (true)
			{
				y += dy[j], x += dx[j];
				if (y < 0 || y >= N || x < 0 || x >= N || Map[y][x] == 84) break;
				if ((O1.first == y && O1.second == x) || (O2.first == y && O2.second == x) || (O3.first == y && O3.second == x)) break;
				if (Map[y][x] == 83) return false;
			}
			y = i.first, x = i.second;
		}
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	vector<vector<int>> Map(N, vector<int>(N));

	char Input;
	for (int y = 0; y < N; ++y)
	{
		for (int x = 0; x < N; ++x)
		{
			cin >> Input;

			switch (Input)
			{
			case 'X': O.push_back({ y, x }); Map[y][x] = 88; break;
			case 'S': S.push_back({ y, x }); Map[y][x] = 83; break;
			case 'T': T.push_back({ y, x }); Map[y][x] = 84; break;
			default: break;
			}
		}
	}

	for (int i = 0; i < O.size(); ++i)
	{
		for (int j = i + 1; j < O.size(); ++j)
		{
			for (int k = j + 1; k < O.size(); ++k)
			{
				if (Func(Map, O[i], O[j], O[k]))
				{
					cout << "YES" << "\n";
					return 0;
				}
			}
		}
	}
	cout << "NO" << "\n";
}