백준 18428번 감시 피하기 C++

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

 

백트래킹을 이용하여 빈 칸에 3개의 장애물을 놓는 모든 경우를 만들고

각각의 경우마다 배열을 검사하면서 하나의 경우라도 선생님의 감시를 피할 수 있다면 YES, 하나도 피할 수 없다면 NO를 출력하도록 구현하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
char arr[6][6];
bool isPossible = false;
int posR[4] = { -1,0,1,0 };
int posC[4] = { 0,1,0,-1 };

bool IsMeet() {
	bool isMeet = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 'S') {
				for (int k = 0; k < 4; k++) {
					int nextRow = i;
					int nextCol = j;
					while (true) {
						nextRow += posR[k];
						nextCol += posC[k];
						if (nextRow < 0 || nextRow >= n) break;
						if (nextCol < 0 || nextCol >= n) break;
						if (arr[nextRow][nextCol] == 'O') break;
						if (arr[nextRow][nextCol] == 'T') {
							isMeet = true;
							return isMeet;
						}
					}
				}
			}
		}
	}
	return isMeet;
}

void BT(int start, int cnt) {
	if (isPossible) return;
	if (cnt == 3) {
		if (!IsMeet()) isPossible = true;
		return;
	}
	for (int i = start; i < n * n; i++) {
		int row = i / n;
		int col = i % n;
		if (arr[row][col] == 'X') {
			arr[row][col] = 'O';
			BT(i + 1, cnt + 1);
			arr[row][col] = 'X';
		}
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	BT(0, 0);
	if (isPossible) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}
};