[BOJ/백준 18428/C++] 감시 피하기

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

18428번: 감시 피하기

 

[문제 요약]

- NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다.

 

- 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다. 또한 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정하자.

 

- 다음 그림에서 S는 학생, T는 선생님, O는 장애물을 의미한다.

- 학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치해야 한다. 결과적으로 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 계산하고자 한다. NxN 크기의 복도에서 학생 및 선생님의 위치 정보가 주어졌을 때, 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력하는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 자연수 N이 주어진다. (3 ≤ N ≤ 6) 둘째 줄에 N개의 줄에 걸쳐서 복도의 정보가 주어진다. 

- 각 행에서는 N개의 원소가 공백을 기준으로 구분되어 주어진다. 해당 위치에 학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X가 주어진다.

- 단, 전체 선생님의 수는 5이하의 자연수, 전체 학생의 수는 30이하의 자연수이며 항상 빈 칸의 개수는 3개 이상으로 주어진다.

- 시간 제한 : 2초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 브루트포스의 방식을 이용하여 문제를 풀 수 있다.

 

장애물은 반드시 3개가 놓여진다.

 

따라서 빈 칸의 좌표들을 vector에 저장하고, 3개의 좌표를 골라 그 위치에 장애물을 놓아보고 선생님들 중 단 한명이라도 학생을 볼 수 있는지 없는지 판별한다음 볼 수 있다면 다음 좌표들의 조합으로 넘어가고(모든 좌표들의 조합으로도 볼 수 있다면 NO를 출력한다 ), 볼 수 없다면 YES를 출력해주면 되는 간단한 문제다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int N;
vector<vector<char>> mp;
vector<pii> blank;
vector<pii> teacher;

bool promising(vector<pii>& input)
{
	vector<vector<char>> dummy = mp;

	for (int i = 0; i < input.size(); i++) dummy[input[i].first][input[i].second] = 'O';

	for (int i = 0; i < teacher.size(); i++)
	{
		pii tmp = teacher[i];
		int row = tmp.first; int col = tmp.second;
		//하
		for (int j = row + 1; j < N; j++)
		{
			if (dummy[j][col] == 'S') return false;
			else if (dummy[j][col] == 'O') break;		
		}
		//상
		for (int j = row - 1; j >= 0; j--)
		{
			if (dummy[j][col] == 'S') return false;
			else if (dummy[j][col] == 'O') break;
		}
		//우
		for (int j = col + 1; j < N; j++)
		{
			if (dummy[row][j] == 'S') return false;
			else if (dummy[row][j] == 'O') break;
		}
		//좌
		for (int j = col - 1; j >= 0; j--)
		{
			if (dummy[row][j] == 'S') return false;
			else if (dummy[row][j] == 'O') break;
		}
	}
	return true;
}

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

	cin >> N;
	mp.resize(N);
	for (int i = 0; i < N; i++) mp[i].resize(N);

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (mp[i][j] == 'X') blank.push_back({ i,j });
			else if (mp[i][j] == 'T') teacher.push_back({ i,j });
		}
	}
		

	for (int s1 = 0; s1 <= blank.size() - 3; s1++)
	{
		for (int s2 = s1 + 1; s2 <= blank.size() - 2; s2++)
		{
			for (int s3 = s2 + 1; s3 <= blank.size() - 1; s3++)
			{
				vector<pii> object;
				object.push_back(blank[s1]);
				object.push_back(blank[s2]);
				object.push_back(blank[s3]);
				if (promising(object))
				{
					cout << "YES";
					return 0;
				}
			}
		}
	}
	cout << "NO";

	return 0;
}

굳