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

https://www.acmicpc.net/submit/18428/32818300

로그인

14502번 연구소와 비슷했던 문제, DFS와 구현력을 요구하는 문제였다.

 

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

int N;
char map[7][7];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool flag;
vector<pair<int, int> > teacher, blank;

bool canWatch(int nx, int ny, int dir) {
	while(1) {
		nx += dx[dir], ny += dy[dir];
		if(map[nx][ny] == 'O' || nx < 0 || nx >= N || ny < 0 || ny >= N) break; // 장애물을 만나거나, 범위를 벗어나면 종료 
		if(map[nx][ny] == 'S') return true; // 학생을 만나면 감시 성공  
	}
	
	return false; // 감시 실패 
}

bool isPossible() {
	for(int i = 0; i < teacher.size(); i++) {
		int x = teacher[i].first;
		int y = teacher[i].second;
		
		for(int j = 0; j < 4; j++) {
			if(canWatch(x, y, j)) return false; // 감시를 성공한다면 학생이 감시 피하기 실패 
		} 
	}
	
	return true; // 감시를 전부 피했으므로 성공 
}

void DFS(int cnt) {
	if(cnt == 3) {
		if(isPossible()) flag = true;
		return;
	}
	
	for(int i = 0; i < blank.size(); i++) {
		int x = blank[i].first;
		int y = blank[i].second;
		if(map[x][y] == 'X') {
			map[x][y] = 'O';
			DFS(cnt + 1);
			map[x][y] = 'X';
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    
	cin >> N;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> map[i][j];
			if(map[i][j] == 'T') teacher.push_back({ i, j });
			else if(map[i][j] == 'X') blank.push_back({ i, j });
		}
	}
	
	DFS(0);
	if(flag) cout << "YES";
	else cout << "NO";
}