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

Pixabay로부터 입수된 Tumisu님의 이미지 입니다.

 

---

 

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

18428번: 감시 피하기

 

 이번 문제는 N과 NxN 크기의 복도 구조가 주어질 때, 장애물을 단 3개만 설치해서 모든 학생들이 감시당하지 않을 수 있는지를 알아내는 문제이다. 우선 장애물과 관련된 사항들을 살펴보자. 

• 무조건 3개의 장애물을 설치해야 한다.
• 빈 칸('X')에만 장애물을 설치할 수 있다.
• 선생님은 장애물 뒤편은 감시할 수 없다.

장애물을 설치하는 데에 있어 특별히 신경써야 할 부분은 없다. 그리고 장애물을 설치하기 좋은 곳을 판별하는 방법이나 알고리즘이 있다면 적용하고 싶지만 이런 것은 없는 것 같다. 그렇기에 일일이 빈 칸에 장애물을 3개씩 설치해야 한다. 

 

 장애물을 설치는 조합의 원리를 이용할 것이다. 조합은 원소의 순서가 바뀌어도 같은 것으로 취급한다. 예를 들어, 1부터 10까지 숫자 중, { 1, 2 }를 선택하는 것과 { 2, 1 }을 선택하는 것은 같은 경우이다.

 

void Obstacle(int idx, int cnt)
{
	if (cnt >= 3)
	{	
		bool success = Check();
		
		if (success) 
			answer = true;

		return;
	}
	
    // 아래의 두 return은 무의미한 탐색을 하지 않기 위함
    
    // 이미 모든 학생이 감시당하지 않는 것을 아는 경우 바로 중단한다.
	if (answer == true)
		return;
	
    // idx가 빈 칸 좌표들의 크기보다 클 경우 바로 중단한다.
	if (idx >= blanks.size())
		return;

	int r = blanks[idx].first;
	int c = blanks[idx].second;
	
    // 현재 빈 칸에 장애물을 설치했을 경우
	corridor[r][c] = OBST;
	Obstacle(idx + 1, cnt + 1);
	
    // 현재 빈 칸에 장애물을 설치하지 않았을 경우
	corridor[r][c] = EMPTY;
	Obstacle(idx + 1, cnt);
}

이 함수의 blanks는 입력으로 주어진 빈 칸의 좌표들이며 corridor는 입력으로 주어진 2차원 배열이다. 이 함수는 모든 빈 칸 좌표들 중 3개를 선택해 감시 결과를 체크하는 함수이다. 현재 빈 칸에 장애물을 설치한 경우와 그렇지 않은 경우를 나누어서 탐색을 진행한다.

 

 

 다음은 감시 결과를 체크하는 부분이다.

int nr[4] = { 1, -1, 0, 0 };
int nc[4] = { 0, 0, 1, -1 };

bool Check()
{
	for (int t = 0; t < teachers.size(); ++t)
	{
		pair<int, int> teacher = teachers[t];

		for (int i = 0; i < 4; ++i)
		{
			int nxtR = teacher.first + nr[i];
			int nxtC = teacher.second + nc[i];

			while(IsInside(nxtR, nxtC))
			{
				if (corridor[nxtR][nxtC] == 'S')
					return false;
				else if (corridor[nxtR][nxtC] == 'O')
					break;

				nxtR += nr[i];
				nxtC += nc[i];
			}
		}
	}

	return true;
}

이 함수의 teachers는 입력으로 주어진 선생님들의 좌표들이다. 선생님들은 상, 하, 좌, 우 4방향으로, 장애물이 없는 한 복도 끝까지 감시가 가능하다. 이 때, 만약 학생을 감시하게 된다면 문제의 조건인 '모든 학생들을 감시로부터 피하도록'을 충족할 수 없으므로 바로 false를 반환하면서 끝을 낸다. 그리고 모든 학생이 걸리지 않았다면 마지막에 true를 반환하게 된다.

 

 

 전체적으로 어렵지 않은 문제였다. 모든 코드는 다음과 같다.

#include <iostream>
#include <vector>
#pragma warning(disable:4996)
#define MAX 7
#define OBST 'O'
#define EMPTY 'X'
using namespace std;

int N;
bool answer = false;
vector<vector<char>> corridor;
vector<pair<int, int>> teachers;
vector<pair<int, int>> blanks;

int nr[4] = { 1, -1, 0, 0 };
int nc[4] = { 0, 0, 1, -1 };

bool IsInside(int r, int c)
{
	return 1 <= r && r <= N && 1 <= c && c <= N;
}

bool Check()
{
	for (int t = 0; t < teachers.size(); ++t)
	{
		pair<int, int> teacher = teachers[t];

		for (int i = 0; i < 4; ++i)
		{
			int nxtR = teacher.first + nr[i];
			int nxtC = teacher.second + nc[i];

			while(IsInside(nxtR, nxtC))
			{
				if (corridor[nxtR][nxtC] == 'S')
					return false;
				else if (corridor[nxtR][nxtC] == 'O')
					break;

				nxtR += nr[i];
				nxtC += nc[i];
			}
		}
	}

	return true;
}

void Obstacle(int idx, int cnt)
{
	if (cnt >= 3)
	{	
		bool success = Check();
		
		if (success) 
			answer = true;

		return;
	}

	if (answer == true)
		return;

	if (idx >= blanks.size())
		return;

	int r = blanks[idx].first;
	int c = blanks[idx].second;

	corridor[r][c] = OBST;
	Obstacle(idx + 1, cnt + 1);

	corridor[r][c] = EMPTY;
	Obstacle(idx + 1, cnt);
}

int main()
{
 	ios_base::sync_with_stdio(0);
	std::cout.tie(0);
	std::cin.tie(0);

	cin >> N;

	corridor.resize(N + 1, vector<char>(N + 1, EMPTY));

	for (int r = 1; r <= N; ++r)
	{
		for (int c = 1; c <= N; ++c)
		{
			cin >> corridor[r][c];

			if (corridor[r][c] == 'T')
				teachers.push_back({ r, c });
			else if (corridor[r][c] == 'X')
				blanks.push_back({ r, c });
		}
	}

	Obstacle(0, 0);
	
	if (answer) 
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}

 

---

- 조합 구현하기

https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)