[백준] 18428 감시 피하기
문제
- NxN 크기의 복도
- 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행
- 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다
- 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정
- 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력
입력
자연수 N(3 ≤ N ≤ 6)
학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X
출력
첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력
모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력
풀이
처음에는 어떻게 접근해야할지 막막했다. 선생님들의 위치에서 학생들의 위치를 빼서 다 찾아봐야했나 싶었는데, 위의 링크를 통해서 N이 X로 되어있는 빈칸에 장애물을 하나씩 두면서 3개가 되었을 때 모든 학생들이 다 가려지는지 확인하는 DFS방법으로 진행
- 선생님과 빈칸 각각을 T(teacher), B(blank)배열에 저장
- 빈칸을 dfs 탐색하면서 탐색한 곳에 장애물 표시
- 장애물 개수가 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;
}
Author And Source
이 문제에 관하여([백준] 18428 감시 피하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@botong_99/백준-18428-감시피하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)