[백준] 18428 감시 피하기

백준18428링크
아이디어참고링크

문제

• NxN 크기의 복도
• 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행
• 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다
• 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정
• 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력

입력

자연수 N(3 ≤ N ≤ 6)
학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X

출력

첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력
모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력

풀이

처음에는 어떻게 접근해야할지 막막했다. 선생님들의 위치에서 학생들의 위치를 빼서 다 찾아봐야했나 싶었는데, 위의 링크를 통해서 N이 X로 되어있는 빈칸에 장애물을 하나씩 두면서 3개가 되었을 때 모든 학생들이 다 가려지는지 확인하는 DFS방법으로 진행

1. 선생님과 빈칸 각각을 T(teacher), B(blank)배열에 저장
2. 빈칸을 dfs 탐색하면서 탐색한 곳에 장애물 표시
3. 장애물 개수가 3개가 되었을 때 선생님들한테 가려지는지 확인하는 함수(checkStudent)로 확인 -> 각 선생님들의 상하좌우로 복도 크기 내에서 장애물 사이에 학생이 있는 경우 false 리턴, 모두 조건을 만족하는 경우 true 리턴

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

#define MAXN 6

using namespace std;

char g[MAXN][MAXN];
vector<pair<int, int>> t,b; //teacher,blank

int N;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

bool checkStudent(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x;
		int ny = y;

		while (nx >= 0 && ny >= 0 && nx < N && ny < N) { //한방향으로 계속 이동하면서 체크하기
			if (g[nx][ny] == 'O') break;
			if (g[nx][ny] == 'S') return false;
			nx += dx[i];
			ny += dy[i];
		}
	}

	return true;
}

void DFS(int count, int idx) {

	if (count == 3) {
		for (int i = 0; i < t.size(); i++) {
			if (!checkStudent(t[i].first, t[i].second)) {
				return;
			}
		}
		cout << "YES";
		exit(0);
	}

	for (int i = idx; i < b.size(); i++) {
		g[b[i].first][b[i].second] = 'O';
		DFS(count + 1, i + 1);
		g[b[i].first][b[i].second] = 'X';
	}
	return;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >>g[i][j];
			if (g[i][j] == 'T') {
				t.push_back(make_pair(i, j));
			}
			else if (g[i][j] == 'X') {
				b.push_back(make_pair(i, j));
			}
		}
	}

	DFS(0, 0);

	cout << "NO";

	return 0;
}