BOJ - 18428번 감시 피하기 (C++)

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

문제 난이도

Silver 1

문제 접근법

완전 탐색 문제다! 게다가 배열 범위도 작아서 일일이 장애물을 두고 계산할 수 있다.
여기서 팁은 X, 비어있는 공간만 따로 모아서 이 빈 공간에만 장애물을 둔다.

통과 코드

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

#define INF 987654321

using namespace std;

char arr[6][6];
int dy[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
vector<pair<int,int>> e, t;
int N;

bool ch(int x,int y) {
	for (int k = 0; k < 4; k++) {
		int nx = x;
		int ny = y;
		while (nx >= 0 && ny >= 0 && nx < N && ny < N) {
			if (arr[nx][ny] == 'O') break;
			if (arr[nx][ny] == 'S') return false;
			nx += dy[k][0];
			ny += dy[k][1];
		}
	}
	return true;
}

void dfs(int cnt,int idx) {
	if (cnt == 3) {
		for (auto x : t) {
			if (!ch(x.first, x.second)) {
				return;
			}
		}
		cout << "YES\n";
		exit(0);
	}
	for (int i = idx; i < e.size(); i++) {
		arr[e[i].first][e[i].second] = 'O';
		dfs(cnt + 1, i+1);
		arr[e[i].first][e[i].second] = 'X';
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'T') {
				t.push_back({ i,j });
			}
			else if (arr[i][j] == 'X') {
				e.push_back({ i,j });
			}
		}
	}
	dfs(0, 0);
	cout << "NO\n";

	return 0;
}